# What does the phrase 'up to logarithmic factors' mean when discussing algorithm time complexity?

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?

• It means the true complexity is (log M + log N) times more than the specified complexity. – user43170 May 13 '18 at 1:14
• @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? – Greenstick May 13 '18 at 1:23
• More likely, since log is asymptotically smaller than any power of n, the authors thought this put too much emphasis on it. – Michaël Cadilhac May 13 '18 at 6:49
• The extra factor may be $(\log n +\log m)^c$ for some constant $c$. – Emil Jeřábek May 13 '18 at 7:53
• Ah I see, thanks! If anyone would like to write this up as answer I’ll accept it. – Greenstick May 13 '18 at 16:29