Master of Information Technology @ The University of Melbourne

0%

## 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