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

- Concept

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