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 , where is the size of the array. We have seen that a code snippet that contains 2 loops is proportional to . And we have seen that halving the input in every iteration is proportional to . 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 , the answer is YES an estimate is sufficient!
In one of the articles, we found an algorithm that has a running time of . If we take a look at the graph of versus , we will see that is greater than .
This means that is bounded above by . To generalize this concept, we define what is known as the “Big Oh” approximation. Given two functions and , we say that f is of order g, written is , if and only if, there exist a positive real number and a real number such that for all ,
, whenever .
Using this definition, we can show that is . Expanding
By taking , we have shown that .
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
Since and for , we have
. By taking and , we have
. Therefore, the binary search algorithm is .