In analysis of PSRS Why O(p^2 log p^2) = O(p^2 log p)?
Analysis of PSRS (Parallel sorting by regular sampling) In Computation part. Why Big-o of Sorting regular samples : O(p^2 log p^2) =开发者_如何学C O(p^2 log p) ? Thank you for answering.
Because log p² = 2 log p (that's a property of logarithms) and using Big-O notation lets you ignore the multiplicative constant.
O(p^2 log p^2) = O(2p^2 log p), by properties of logarithms. And O(kg) = O(g) where k is a constant. Therefore you can remove the 2 to arrive at O(p^2 log p).
精彩评论