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

Question

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

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? http://www.wolframalpha.com/input/?i=Plot[{n^2,+n^2*2^Log[n]},+{n,+0,+50}] — Thanos Tintinidis, May 11 '16 at 14:54
Seems like this is more fit for [cstheory.se], [cs.se] or even [math.se]. — cat, May 11 '16 at 16:51
@cat Yes, I was thinking about it (short), but then I notices the big-o-tag here and thought "OK, can't be that wrong". — palsch, May 11 '16 at 16:53
@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

score 18 · Accepted Answer · answered May 11 '16 at 13:28

18

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.

answered May 11 '16 at 13:28

Sebastian Redl

15,334

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

gnasher729 · Answer 2 · 2016-05-11T16:36:05.637

Assuming that "log" is the natural logarithm:

2^{log (n)} = exp (log 2 * log n) = exp (log n * log 2) = n ^{log (2)}
and O (n² 2^{(log n)}) = O (n^{(2 + log 2)}) ≈ O (n^2.693)

If "log" is the base 10 logarithm, then it is O (n^2.301). If "log" is the base 2 logarithm, then it is O (n³). Write log₁₀ 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.

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

2 Answers2