3
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ What is the difference between M and N? $\endgroup$ Apr 17, 2022 at 14:16
  • $\begingroup$ @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 $\endgroup$ Apr 18, 2022 at 11:02

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thanks @Eelvex, Yes they are independent variables. I have M training vectors that I would like to measure the distance for each of them with a single test vector. All vectors are living in the N dimensions. $\endgroup$ Apr 18, 2022 at 11:04
  • $\begingroup$ So, in this case we can say that both O(N log(M)) and O(log(NM)) are both considered as exponential gain against O(MN) right? Or can we say that O(N log(M)) is exponential gain and O(log(NM)) is super exponential gain ? $\endgroup$ Apr 18, 2022 at 11:05
  • $\begingroup$ I wouldn't call it super exponential, it sounds misleading. I would prefer "O(N log(M)) is exponential on M, O(log(NM)) is exponential on both variables". The bottom line is that as long as you are explicit and precise you may call them whatever you want. $\endgroup$
    – Eelvex
    Apr 18, 2022 at 13:02
  • $\begingroup$ Yes, I understand. Thanks a lot for your help @Eelvex. $\endgroup$ Apr 19, 2022 at 15:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.