What is Time Complexity of An algorithm? : (O-notation)

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

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

N2

Increases fourfold

Bubble sort

Article Written By:
Kamlesh

Reference:

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

Advertisements

4 thoughts on “What is Time Complexity of An algorithm? : (O-notation)

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

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

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s