CODEWITHSUNDEEP
mathbig-otime-complexity
user11001
user11001

Reputation: 372

O notation: 2^log(O(n^2)) = 2^O(log(n^2))?

I tried to solve this with logarithm rules:

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

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

Im not sure that is true?

Upvotes: 2

Views: 125

Answers (2)

templatetypedef
templatetypedef

Reputation: 372814

I think this depends on what the equals sign means here. If the equals sign means

"Any function that is of 2log O(n2) is also 2O(log n2)"

Then the claim is true. Let f(n) be some function that's O(n2). This means that there's a c and n0 such that for any n ≥ n0, we know that f(n) ≤ cn2. Therefore, for any n ≥ n0, we know that

2log f(n) ≤ 2log (cn2) = 2(log c + log n2)

The function log c + log n2 is itself O(log n2), so we see that

2log f(n) ≤ 2(log c + log n2) = 2O(log n2)

On the other hand, if the equals sign means

"The class of functions that is 2log O(n2) is the same class of functions that is 2O(log n2)"

then the claim is false. For example, the function n4 is in the second class because it can be written as 22 log n2, but it's not in the first class.

Hope this helps!

Upvotes: 1

gnasher729
gnasher729

Reputation: 52538

No, no, no. You can't just take logarithms.

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

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

The first is just O (n^2). The second one is n raised to sum unknown but limited power.

Upvotes: 1

Related Questions