开发者

Polynomially larger - confusion

开发者 https://www.devze.com 2023-03-04 22:33 出处:网络
I am studying for my algorithms class. I have a question in context to the Masters theorem: How is n.log2(n) polynomially larger than n^(log4(3))

I am studying for my algorithms class. I have a question in context to the Masters theorem:

How is n.log2(n) polynomially larger than n^(log4(3))

(log2(x) = log to the base 2 of x

 log4(x) = log to the base 4 of x) (Note: This is a solved problem on page.95 of 'Introduction to Algorithms' by Cormen et.开发者_如何学编程al.)


log4(3) is less than 1, and so n^(log4(3)) is less than n^1 = n, which is less than n*log2(n).

0

精彩评论

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