5

I was just told by someone that my code should follow the complexity guideline of O(logn) + O(n). When prompted for clarification, I was presented with, "the complexity of the code :)" In any event, any clarification over and above the provided would be appreciated.

Benjamin Powers
  • 3,186
  • 2
  • 18
  • 23
  • 1
    O(log n) + O(n) = O(n), so I guess that certain someone is referring to combination of specific algorithms or parts of a given algorithm (if there is such). – Gabriel Ščerbák Aug 08 '11 at 01:33

2 Answers2

10
O(logn) + O(n) = O(n)

"I was just told by someone that my code should follow the complexity guideline of O(logn) + O(n)" - without knowing what your code is supposed to do, no one can answer what its reasonable complexity should be.

See Big O notation

Mitch Wheat
  • 295,962
  • 43
  • 465
  • 541
  • Nice! The link led me to http://stackoverflow.com/questions/2473989/list-of-big-o-for-php-functions which provides proper context. I'm messing with array_key_exists, and in_array to solve a programming riddle. I'm still not exactly sure s/he was trying to get at (i.e. is this complexity for the arrays, or for the application as a whole). I also see in http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o/487278#answer-487278 that 0(log n) speaks to a logarithmic complexity, which in the telephone example, seems relevant to arrays. – Benjamin Powers Aug 08 '11 at 02:57
3

Without context, this is rather difficult to answer. "O(logn) + O(n)" by itself makes little sense because the asymptotic complexity of any given algorithm would be dominated by the linear term, so writing "+ O(logn)" doesn't clarify anything.

pg1989
  • 1,010
  • 6
  • 13