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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ What is the difference between M and N? $\endgroup$
    – Mark Spinelli
    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$
    – Yousef Zook
    Apr 18, 2022 at 11:02

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Yousef Zook
    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$
    – Yousef Zook
    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$
    – Yousef Zook
    Apr 19, 2022 at 15:50

Your Answer

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

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