Algorithm Analysis - Time Complexity

Time Complexity Overview

• This chapter introduces how to calculate the time complexity of a algorithm no matter it is recursive or just a normal algorithm.

Normal Algorithm

• How to find the basic operation:
  the innermost
• Expression of Time Complexity
  • O : O(g(n)) means TC is slower than g(n)
  • Omega : O(g(n)) means TC is faster than g(n)
  • Theta : O(g(n)) means TC is same than g(n)
• Calculation Step
  • Basic Operation Efforts * Numbers of execution
  • lim n->Infinity // 求导数
    • Concept
      Ignore constant factors
      Ignore small input sizes
      Think n bigger!!!
      1 ≺loglogn ≺logn ≺n^ε ≺n^c ≺n^logn ≺c^n ≺n^n


      where 0 < ε < 1 < c

Recursive Algorithm

• TC consist of TWO PARTS : ENDING POINT EFFORT + RECURSIVE EFFORT
• EXAMPLE (>>Dueape<<P21)
• Use Telescoping to Calculate the RECURSIVE EFFORT

Master Theorem

• T(n) = aT(n/b) + f(n) f(n) Belongs To Theta(n^d)

  T(n) = Theta(n^d) if a < b^d
  T(n) = Theta(logn * n^d) if a = b^d
  T(n) = Theta(n^logb(a)) if a > b^d