5 ^（log2N）とN ^（1/2）の間の大きなO関係を分析し、証明する方法は？

Question

これはSanjoy Dasguptaの著書「アルゴリズム」の練習問題です。

"指数関数多項式を支配する"ので、5^(log2N)はより複雑です。しかし、私はそれを証明しようとすると混乱しました。

私は2つの比率の制限を計算しようとしましたが、L'Hitalのルールはここではうまくいかないと思われたので失敗しました。

だから、私は2つにlog2を与え、取得しよう：

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

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

結果は私をイライラ。それは2つが同じ複雑さを持っていることを意味しますか？

間違いが起こった場所を指摘できますか？

ありがとうございます！

Answer 1

はい2つが同じcomplexity.Big O記法は非常に非常に大きな値（log2N）のために長いrun.Andにおける挙動を意味する漸近解析のために使用される有し* 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.