# Growth of Function & Asymptotic Notation (Week 3)
**Growth of Function** berelasi terhadap kompleksitas algoritma. Lebih cepat *Growth of Function* lebih tidak efisien.
^{Visualization of GOF}
**Asymptotic Notation** digunakan untuk mengekspresikan kompleksitas algoritma. **Asymptotic Notation** bertujuan untuk mendeskripsikan *running time* atau efisiensi Asymptotic dari sebuah algoritma.
Berikut beberapa jenis **Asymptotic Notation**:
- Big *Oh* (Ο)
- Big *Theta* (Θ)
- Big *Omega* (Ω)
- Little *Oh* (𝜊)
- Little *Omega* (w)

### Big *Oh* (Ο)
*f*(n) = O(*g*(n)) artinya *g*(n) adalah **asymptotic upper bound** for *f*(n).
> O(*g*(n)) = {*f*(n): there exist positive constants *c* and n₀ such that 0<=*f*(n)<=*c* *g*(n) for all n >= n₀}.

^{as 𝑛 grows larger, 𝑓(n) grows slower than 𝑐𝑔(n)}

### Big *Omega* (Ω)
*f*(n) = Ω(*g*(n)) artinya *g*(n) adalah **asymptotic lower bound** for *f*(n).
> Ω(*g*(n)) = {*f*(n): there exist positive constants *c* and n₀ such that 0<=*c* *g*(n)<=*f*(n) for all n >= n₀}.

^{as 𝑛 grows larger, 𝑓(n) grows faster than 𝑐𝑔(n)}

### Big *Theta* (Θ)
*f*(n) = Θ(*g*(n)) artinya *g*(n) adalah **asymptotic tight bound** for *f*(n).
> Θ(*g*(n)) = {*f*(n): there exist positive constants *c*₁, *c*₂ and n₀ such that 0<=*c*₁ *g*(n)<=*f*(n)<=*c*₂ *g*(n) for all n >= n₀}.

### Little *Oh* (𝜊)
Little oh (𝜊) notation is used to denote a not asymptotically tight upper bound.
Example:
- 2𝑛² = Ο(𝑛²) is asymptotically tight
- 2𝑛 = Ο(𝑛²) is not asymptotically tight

### Little *Omega* (w)
Little omega notation is used to denote a not asymptotically tight lower bound.