問題詳情

3. Determine the tightest big-O complexity of the recurrence: T(n)=T(n-1)+1, T(0)=0
(A)O(1)
(B) O(n)
(C) O(nlogn)
(D)O(n2)
(E)O(n3)

參考答案

答案：[無官方正解]
難度：計算中-1
書單：沒有書單，新增

用户評論

【p_p971】評論

Ans: (C) O(nlogn)By Master Theorem:T(n) = T(n-1)+1, 得知 a=1, b =1, d=1.使得, d = log_b^a, => 1 = 1,故, T(n) = O(n^d log n) = O(n log n)