Technical Musings !!

The performance of a data structure depends on many factors such as efficiency of the code, the hardware configuration etc. Generally all the factors are calculated and put in the form of a mathematical expression. For example suppose for a particular sorting technique the running time is given by

2N² + 18.7N + 5

where N is the number of elements being sorted.

But if the efficiency is described in this way, it’s a bit difficult to compare the respective time complexities for different algorithm. Therefore, in order to make our task easier, O-notation (Pronounced as “big-oh notation”) is used. O-notation is a generalization of the complicated expression we get for the time complexity of a particular algorithm. In the above example, with the increase in the number of elements, i.e. N, the N² term becomes significant enough to neglect the rest lower power terms of N. The O-notation in this case is therefore, O(N²). This means, if the number of elements increases by two fold, the time taken increases approximately by four fold in this case.

As we need to know the time complexity mainly to compare two algorithms, so the O-notation technique (even it is an approximate one) proves to be very useful for this purpose.

Some commonly used O-notations with there meaning are given below.

Article Written By:
Kamlesh

Reference:

Generics and Collections in Java 5 – Mauris Naftalin & Philip Wadler