When analyzing PSRS. Why is O (p ^ 2 log p ^ 2) = O (p ^ 2 log p)?

Question

PSRS analysis (parallel sorting using regular sampling) In the calculation part. Why is Big-o sorting regular patterns: O (p ^ 2 log p ^ 2) = O (p ^ 2 log p)? Thanks for answering.

Answer 1

Since log p² = 2 log p (which is a property of the logarithms) and using the Big-O notation you can ignore the multiplicative constant.

Answer 2

O (p ^ 2 log p ^ 2) = O (2p ^ 2 log p), according to the properties of the logarithms. And O (kg) = O (g), where k is a constant. Therefore, you can remove 2 to reach O (p ^ 2 log p).