(1)Time for merge-sort can be modeled as the recursion T(n)=2T(n/2)+cn
that has solution theta(nlogn).And balance recursion achieves the best result.
Thus the lower bound to sorting problem is Omega(nlogn).
這個敘述錯在哪呢?
Merge-sort的best/average/worst case 都是O(nlogn)沒錯
所以是因為是theta的關係嗎?
(2)
long f (long n){
if (n<1) return 0;
if (n<3) return 1;
return f(n-1)+f(n-2);
}
The number of recursive calls grows exponentially with n
這句話的意思是 O(2^n)對嗎?
這和費氏數列的時間複雜度應該是一樣的
(3)
6(n^3)/(logn+1)的時間複雜度為什麼是n^3次呢?
logn跟n^3比太小可以忽略嗎??
希望有人能給個指點謝謝!!