algorithm - 分析5 ^(log2N)与N ^(1/2)之间的大O关系，并如何证明？

这是Sanjoy Dasgupta在《算法》一书中的一个练习。
我猜想5^(log2N)因为“指数支配多项式”更复杂。不过，当我试图证明这一点时，我感到困惑。
我试图计算二者比率的限制，但失败了，因为在这里，拉皮塔尔法则似乎不起作用。
所以，我试着把log2给两个人，得到：

log2[5^log2N]=(log2N)*log2(5)

log2[N^(1/2)]=(1/2)*log2N

结果使我很沮丧。这是否意味着两者具有相同的复杂性？
希望能指出错误发生在哪里？
谢谢！

最佳答案

是的，两个具有相同的复杂度。大O符号用于渐近分析，这意味着长期的行为。对于非常非常大的值（Log2n）*Log2（5）和（1/2）*Log2n将大致相同。你正确地解决了这个问题。

Let 5^log2N be F(N) and N^(1/2) be G(N).

log2(F(N)) = C*log2N, where C=log2(5), This means that

log2(F(N)) <=(C+1)log2N and this means that

log2(F(N)) = O(log2N), because C+1 is also a constant.

Similarly log2(G(N)) = O(log2N)

Now we have F(N) = 2^O(log2N) and G(N) = 2^O(log2N)

This is the reason they have same complexity.