Big O Notation

What is Big O???

Big O notation is a technique used to describe the complexity of an algorithm. It is very useful when evaluating performance wise of different algorithms doing the same task. In this post, I'm not going deep into the programming side but let's take a code snippet as an example.

In this code, we are trying to add up all the natural numbers up to 100. There are two algorithms doing the same job but they perform differently.

#***********************#
# Method 1
n = 100
sum = 0
for i in range(0, n + 1):
    sum = sum + int(i)

print sum

#***********************#
# Method 2
print str(n * (n + 1) / 2)
#***********************#

In Method 1, the program runs 100 times inside the for loop adding up numbers giving out a complexity $O(n)$ where n = 100 while in Method 2, it is just one step with a complexity of $O(1)$. As n grows, the Method 1 takes more and more resources and time while the Method 2 just stick with one step.

Definition

Let $\{x_n\}$ and $\{\alpha_n\}$ be two sequences. We say $x_n = O(\alpha_n)$ as $n\to \infty$ if there are constants $c$ and $y$ such that $|x_n| \le c|\alpha_n|$ where $n\ge y$
Equivalently $x_n = O(\alpha_n)$ iff $\lim_{n\to\infty} \left|\frac{x_n}{\alpha_n}\right| \le c$

Example

Show that $f(h) = \cos(h)-1+\frac{h^2}{2}$ is $O(h^4)$

We can expand $\cos(h)$ using Taylor Series. $$\cos(h) = 1 + \frac{1}{1!}(-\sin 0)(h)^1 + \frac{1}{2!}(-\cos 0)(h)^2 + \frac{1}{3!}(\sin 0)(h)^3 + \frac{1}{4!}(\cos 0)(h)^4 + ...$$ $$\cos(h) = 1 - \frac{1}{2!}(h)^2 + \frac{1}{4!}(h)^4 + ...$$ $$\therefore f(h) = \frac{1}{4!}(h)^4 - \frac{1}{6!}(h)^6 + ...$$ $$\lim_{h\to\infty} \left|\frac{\frac{1}{4!}(h)^4 - \frac{1}{6!}(h)^6 + ...}{h^4}\right|\le \frac{1}{4!}$$