Time Complexity Analysis

Algorithm's running time as a function of input size n

T(n): worst case run time of algorithm with input size n

• we only care about the dominating term for large n
• we only care about the order instead of exact number

Big-O: Asymptotic upper bound of time complexity

T(n) is O(g(n)) if there exist a constant C, n0 >= 0 such that T(n) ≤ c*g(n) for all n ≥ n0

Big-Ω : Asymptotic lower bound

T(n) is Ω (f(n)) if there exist a c > 0, n0 ≥ 0 such that T(n) ≥ c*f(n) for all n ≥ n0

Big-θ: Asymptotic tight bound:

T(n) is θ(f(n)) if T(n) = O(f(n)) and T(n) = Ω(f(n))

Properties:

Transitivity

• Upper bounds: if f=O(g), and g=O(h), then f=O(h)
• Lower bounds: if f=Ω(g), and g=Ω(h), then f=Ω(h)
• Tight bounds:  if f=Θ(g), and g=Θ(h), then f=Θ(h)

Sum of Functions

• Suppose that f and g are two functions and for some other function h, we have f=O(h) and g=O(h). Then f+g=O(h).