I've come across a few papers that discuss the upper bound of algorithmic time complexity and state something to the effect: 'This algorithm solves the problem in $O(\sqrt{N} + \sqrt{M})$, up to logarithmic factors.'

An example can be seen in this abstract.

The question: in layman's terms, what exactly is meant by (the constraint?) 'logarithmic factors' when discussing algorithmic complexity?

  • $\begingroup$ It means the true complexity is (log M + log N) times more than the specified complexity. $\endgroup$ – user43170 May 13 '18 at 1:14
  • $\begingroup$ @user43170 Could you elaborate a bit? For example, does that mean the true complexity is $(log M + log N)(\sqrt{M}+\sqrt{N})$? If so, why not state that as the complexity — does it have to do with it being a constraint? $\endgroup$ – Greenstick May 13 '18 at 1:23
  • 1
    $\begingroup$ More likely, since log is asymptotically smaller than any power of n, the authors thought this put too much emphasis on it. $\endgroup$ – Michaël Cadilhac May 13 '18 at 6:49
  • 3
    $\begingroup$ The extra factor may be $(\log n +\log m)^c$ for some constant $c$. $\endgroup$ – Emil Jeřábek May 13 '18 at 7:53
  • $\begingroup$ Ah I see, thanks! If anyone would like to write this up as answer I’ll accept it. $\endgroup$ – Greenstick May 13 '18 at 16:29

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.