對數與權力的漸近複雜性

Question

嘿，我正在研究Dasgupta算法書中的一些大問題，並且我堅持了幾個。

1）F（N）= N ^將0.1g（N）=（log n）的^ 10

據對Asymptotic Complexity of Logarithms and Powers頂端答案， 「的log（n）^一個總是爲O（n^b），對於任何正常數a，b。「 因此，對於1）中，f =歐米加（克）

2） F（N）= N ^1.01克（N）= N日誌^ 2 n個 我的猜測爲f =ω-（克）。這個例子是正確的還是不同的情況，因爲log是平方的並且乘以n？

請提供您需要解決這些類型的問題

Answer 1

你回答的第一個問題是正確的步驟任何解釋，因爲是你該規則的應用。 下面是登錄證明（N）= O（N ^一）任何一個> 0（這顯然等同於說規則）：

The derivative of n^a is a*(n^(a-1)) 
The derivative of log(n) = 1/n 
Therefore, for large enough n, the derivative of n^a is more than the derivative of log(n) 
Therefore, for large enough n, n^a > log(n) 
Therefore log(n) = O(n^a) 

你的回答了第二個問題是正確的。這裏有一個證明：

g(n) = O(f(n)) if and only if log(log(n)) = O(n^0.01) 
log(log(n)) = O(log(n)) so log(log(n)) = O(O(n^0.01)) = O(n^0.01)