# The Big Oh!

We have demonstrated how basic counting is used to determine the running time of our algorithms. We have seen that the running time of traversing an array element by element is proportional to $n$, where $n$ is the size of the array. We have seen that a code snippet that contains 2 loops is proportional to $n^2$. And we have seen that halving the input in every iteration is proportional to $\log_2 n$. Do we really need to know the exact number of comparisons in order to determine the running time of an algorithm? Or is an estimate sufficient? For a sufficiently large $n$, the answer is YES an estimate is sufficient!

In one of the articles, we found an algorithm that has a running time of $\frac{n(n+1)}{2}$. If we take a look at the graph of $\frac{n(n+1)}{2}$ versus $n^2$, we will see that $n^2$ is greater than $\frac{n(n+1)}{2}$.

This means that $\frac{n(n+1)}{2}$ is bounded above by $n^2$. To generalize this concept, we define what is known as the “Big Oh” approximation. Given two functions $f(x)$ and $g(x)$, we say that f is of order g, written $f(x)$ is $O(g(x))$, if and only if, there exist a positive real number $M$ and a real number $x_0$ such that for all $x > x_0$,

$\displaystyle |f(x)| \le M\cdot |g(x)|$, whenever $x > x_0$.

Using this definition, we can show that $\frac{n(n+1)}{2}$ is $O(n^2)$. Expanding

$\displaystyle \frac{n(n+1)}{2} = \frac{n^2 + n }{2}$
$\displaystyle \frac{n^2 + n }{2} \le \frac{n^2 + n^2}{2} = \frac{2n^2}{2} = n^2$

By taking $M = 1$, we have shown that $\frac{n(n+1)}{2} = O(n^2)$.

Another example would be computing the Big Oh of the binary search. We have seen in this post that the running time of the binary search is

$\displaystyle a_n = \lfloor \log_2 n \rfloor + 1$

Since $\lfloor \log_2 n \rfloor \le \log_2 n$ and $\log_2 n > 1$ for $n > 2$, we have

$\displaystyle a_n = \lfloor \log_2 n \rfloor + 1 \le \log_2 n + \log_2 n = 2\log_2 n$. By taking $M=2$ and $x_0 = 2$, we have

$\displaystyle |a_n| \le 2\cdot \log_2 n$. Therefore, the binary search algorithm is $O(\log_2 n)$.