Master of Information Technology @ The University of Melbourne

0%

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