CareerCup

both are same

x^log n base x = x
so here 2nd expression = n^2

is this question given inside an onsite interview? i'm just wondering how it can be read through telephone....

say p = logq base 2
2^p = q
similarly
4^log n base 2 = 2^ (2 x log n base 2) = 2^ (log n^2 base 2) = n^2

Is this question asked in USA or India?

I think both are same.

they are the same. it doesn't matter what individual cases evaluate to, what matters is what they converge to.

by the way, the expression above is wrong: x^log n base x = x
It should be x^log n base x = n

x=4^(log n base 2)
x=2^(2log n base 2)
x=2^(log (n^2) base 2)
x=(n ^ 2) ; correlate to e ^ ( ln x) is x

Hence both are same.

Notion: log means log to the base of 2

n^2 = 4^(logn)

Prove:

put log to two sides of equation

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

log(4^(logn)) = log(n) * log4 = log(n) * 2

I dont think that o(n^2) is equal to another o(n^2) point being n^2 and 500n^2 + 500n + 500 both are n^2 but you know what grows faster.

O(n^2) grows faster

both are same. Put some value for n - say 16

O(4^2) = O(16)
O(4^log4 base 2) = O(4^2) = O(16)

I don't think so.
For n = 5, n^2 = 25
where as 4 ^ (log 5 base 2) < 25.

So, O(n^2) grows faster.