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

6
  • 5
    That kind of rough rule of thumb does not apply to multiplication by a non-constant term. May 11, 2016 at 13:20
  • How about comparing them directly? wolframalpha.com/input/?i=Plot[{n^2,+n^2*2^Log[n]},+{n,+0,+50}] May 11, 2016 at 14:54
  • 3
    That's an awful title.
    – cat
    May 11, 2016 at 16:51
  • Seems like this is more fit for Theoretical Computer Science, Computer Science or even Mathematics.
    – cat
    May 11, 2016 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, 2016 at 16:54

2 Answers 2

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.

1
  • It's base 10 (in decimal), but right. Thank you.
    – palsch
    May 11, 2016 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.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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