2

Is O(n^2 * 2^(log n)) == O(n^2) ?

Why I think that this could be the case: In big O, you only take the parts of the term that are most relevant, right? O(n^2 + 3n + 9) == O(n^2). The n^2 has a lot more influence to the result of the term than the 2^(log n)-part. http://www.wolframalpha.com/input/?i=Plot%5B%7Bn%5E2,+2%5ELog%5Bn%5D%7D,+%7Bn,+0,+50%7D%5D

  • 5
    That kind of rough rule of thumb does not apply to multiplication by a non-constant term. – RemcoGerlich May 11 '16 at 13:20
  • How about comparing them directly? wolframalpha.com/input/?i=Plot[{n^2,+n^2*2^Log[n]},+{n,+0,+50}] – Thanos Tintinidis May 11 '16 at 14:54
  • 3
    That's an awful title. – cat May 11 '16 at 16:51
  • Seems like this is more fit for Theoretical Computer Science, Computer Science or even Mathematics. – cat May 11 '16 at 16:51
  • 3
    @cat Based on this, TCS is definitely out - you don't need a degree to reason about polynomials. CS would be a better fit, yes, but there are way too many precedents on both SO and here with questions about Big-O to reject this. – Ordous May 11 '16 at 16:54
17

Your reasoning is incorrect. The rule that you can discard irrelevant terms only applies to additive terms, but in your case the parts are multiplied.

If the logarithm in your case has base 2, 2^ld(n) is actually n, so the total complexity is n^3, which most definitely is not n^2.

| improve this answer | |
  • It's base 10 (in decimal), but right. Thank you. – palsch May 11 '16 at 15:04
10

Assuming that "log" is the natural logarithm:

2log (n) = exp (log 2 * log n) = exp (log n * log 2) = n log (2)
and O (n2 2(log n)) = O (n(2 + log 2)) ≈ O (n2.693)

If "log" is the base 10 logarithm, then it is O (n2.301). If "log" is the base 2 logarithm, then it is O (n3). Write log10 or ln or ld to make clear what you mean. Often the difference is irrelevant, but in this case it is obviously important.

And you don't "take only the parts that are most relevant". You can ignore parts that don't increase the result by more than a bounded factor. Here, the factor 2(log n) is clearly not a bounded factor.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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