开发者

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).

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜