Big O notation O(p^2 log p)

Question

Please help me to describe and solve that why

Θ(p^2 log p^2) = Θ(p^2 log p)

I really got stun on it.

Answer 1

I presume because log(x^n) = nlog(x). And n is a constant, therefore not relevant in Big O. To put it another way, O(n) = O(2n) because they're both twice as bad when n doubles.

Answer 2

It is always good to start with definition! Wiki:

Big-O notation describes the limiting behavior of a function when the argument tends towards a particular value or infinity

Limiting behavior is same for functions f and g, if g = C*f. Asymptotically they behave the same. Now to log. Remeber the formula:

log_bx^y = y log_bx

It means that they are different only by constant, which doesn't change limitting behavior.

But it is importand to remember that their speed and amount of operations are still different (by constant).

Answer 3

log (p^2) = 2 log p (as in general, log (n^m) = m log n)

Since 2 is just a constant, we have that Θ(log p^2) = Θ(log p).

Therefore, we get Θ(p^2 log p^2) = Θ(p^2 log p).

Answer 4

If x = log p^2 that means that e^x = p^2. That means that sqrt(e^x) = p, and so e^(x*1/2) = p. So (log p^2)/2 = log p. This means that p^2 log p^2 = 2 p^2 log p; since this is big-theta constant multipliers can be discarded, so they turn out equivalent.