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).


Published by

Bobby Corpus

Loves to Compute!

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s