ForgotMyCode

Home

Advanced Algorithm Analysis

#1: Introduction

Into

We usually care about space or time in asymptotic manner to express an algorithm’s scalability.

Math notation is used, commonly Big O notation. Basic algorithms, basics of algorithm analysis, calculus.

The notation, formal definition

1.) We say $f(n) \in O(g(n))$ iff there exists $c > 0$ and $n_{0}$, such that $f(n) \leq cg(n)$ for all $n \geq n_{0}$.

2.) We say $f(n) \in \Omega(g(n))$ iff there exists $c > 0$ and $n_{0}$, such that $f(n) \geq cg(n)$ for all $n \geq n_{0}$.

3.) We say $f(n) \in \Theta(g(n))$ iff there exists $c_{1} > 0$, $c_{2} > 0$ and $n_{0}$, such that $c_{1}g(n) \leq f(n) \leq c_{2}g(n)$ for all $n \geq n_{0}$.

4.) We say $f(n) \in o(g(n))$ iff there exists $n_{0}$ for all $c > 0$, such that $0 \leq f(n) < cg(n)$ for all $n \geq n_{0}$.

5.) We say $f(n) \in \omega(g(n))$ iff there exists $n_{0}$ for all $c > 0$, such that $0 \leq cg(n) < f(n)$ for all $n \geq n_{0}$.

Asymptotic bounds

6.) $f(n) \in o(g(n))$ iff $\lim_{n\rightarrow \infty }\frac{f(n)}{g(n)} = 0$.

7.) $f(n) \in \omega(g(n))$ iff $\lim_{n\rightarrow \infty }\frac{f(n)}{g(n)} = \infty$.

8.) $f(n) \in \Theta(g(n))$ iff $\lim_{n\rightarrow \infty }\frac{f(n)}{g(n)} \in \mathbb{R}\setminus \{ 0 \}$.

Implications

What are implications of a function’s property being in $o$ for $O$, or $\omega$ for $\Omega$? How about $\Theta$?