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^{2 }+ 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^{2 }term becomes significant enough to neglect the rest lower power terms of N. The O-notation in this case is therefore, O(N^{2}). 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.

O(…) |
Effect on the running time if N is doubled |
Example algorithm |

1 |
unchanged |
Insertion into a Hash table |

Log N |
Increases by a constant amount |
Insertion into a Tree |

N |
doubled |
Linear Search |

N log N |
Doubled plus a constant amount |
Merge sort |

N |
Increases fourfold |
Bubble sort |

**Article Written By:**

Kamlesh

**Reference:**

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

very helpful article, short and to the point.

we need more of such articles 🙂

really good article, also requests u to write some short article about calculating time complexities for real world problem…

Good for interviews.

–Gautam

http://fast-code.sourceforge.net/

hey dude

i was just going through this book

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

have you finished it???

if yes, you may be of immense help to this gareeb guy.

thanks n regards

mowgli