# O(N log(M)) vs O(log(MN)) Complexity Name

I have a quantum system that solves a problem that takes $$O(MN)$$ on a classical computer. However, because it is solved using a quantum algorithm, it takes $$O(\log(MN))$$.
I also have another algorithm that solves it in $$O(N \log(M))$$.
So my question is: Since $$O(\log(MN)) < O(N \log(M))$$, can we say that both algorithms are making "exponential gain"?
I mean, in complexity-context names, what should we call the gain $$O(\log(MN))$$? and what should we call the gain $$O(N \log(M))$$?

To be specific, I have an algorithm that measures the distance between M training vector and 1 test vector. Each vector is with N dimensions.

• What is the difference between M and N? Apr 17, 2022 at 14:16
• @MarkS I have edited the questions. But you can say that N is a vector dimensions number (ex. 2 , 4 ..etc) and M is the number of vectors Apr 18, 2022 at 11:02

It depends on the relation between N and M. If they are independent you specify the complexity separately: O(N log(M)) is linear on N, logarithmic on M. If they are not independent then you should write the dependencies explicitly.