NC Note:Time complexity

Chapter 2: Binary Search

1. Binary search time complexity:

T(n) = T(n/2) + O(1)
     = T(n/4) + O(1) + O(1)
     = T(n/8) + O(1) * 3
     = T(n/16) + O(1) * 4
     ...
     = T(1) + O(1) * logn 

     = O(logn) 

2. T(n)=T(n/2)+O(n)

T(n) = T(n/2) + O(n)
     = T(n/4) + O(n/2) + O(n)
     = T(n/8) + O(n/4) + O(n/2) + O(n)
     = ...
     = O(1) + O(2) + ... O(n/2) + O(n)
     = O(1 + 2 + 4 .. + n/2 + n)
     = O(2n) = O(n)

许多同学会拍脑袋认为这个式子的结果是 O(nlogn)，这是错误的。主要错在，当 T(n/2) 往下继续展开的时候，很多同学直接写成 T(n/4) + O(n)，这是不对的。应该是 T(n/4) + O(n/2)。这里我们暂时不能约掉 O(n/2) 里的 /2。因为会导致误差累积。

另外一个需要记住的结论就是：O(1 + 2 + 4 ... + n/2 + n) = O(n)。 geometric sequence sum Sn = a1 * (1 - q^n) / (1 - q)

3. Merge sort

T(n) = 2 * T(n / 2) + O(n)

T(n) = 2 * T(n/2) + O(n)
     = 2 * (2 * T(n/4) + O(n/2)) + O(n)
     = 4 * T(n/4) + 2 * O(n/2) + O(n)
     = 4 * T(n/4) + 2 * O(n)
     = 4 * (2 * T(n/8) + O(n/4)) + 2 * O(n)
     = 8 * T(n/8) + 3 * O(n)
     = 16 * T(n/16) + 4 * O(n)
     ...
     = n * T(1) + logn * O(n)
     = O(n) + O(nlogn)
     = O(nlogn)

4. T(n)=2∗T(n/2)+O(1)

T(n) = 2 * T(n/2) + O(1)
     = 2 * (2 * T(n/4) + O(1)) + O(1)
     = 4 * T(n/4) + O(2 + 1)
     = 8 * T(n/8) + O(4 + 2 + 1)
     ...
     = n * T(1) + O(n/2 + n/4 + ... + 2 + 1)
     = O(n) + O(n)
     = O(n)

 4. int Fibo(int n) {

    if (n == 0 || n == 1) return 1;
    return Fibo(n - 1) + Fibo(n - 2);
}

时间复杂度为 $O(2^\frac{n}{2})$ ~ $O(2^n)$

计算时间复杂度上界：$Fibo(n) = Fibo(n-1) + Fibo(n-2) < 2 * Fibo(n-1)$
也就是说，递归版 Fibonacci 的时间复杂度 < $T(n) = 2 * T(n-1) + O(1) = O(2^n)$

再来计算时间复杂度下界：$Fibo(n) = Fibo(n-1) + Fibo(n-2) > 2 * Fibo(n-2)$
也就是说，递归版 Fibonacci 的时间复杂度 > $T(n) = 2 * T(n-2) + O(1) = O(2^\frac{n}{2})$