Big (O) Notation Explained

Firstly, before talking about Big O Notation we should try to answer the following question,

“How do we compare different algorithm implementations in order to choose the best solution for our application?”

It’s simply by Run-time. We need to find algorithm which takes the minimum amount of run-time to solve that particular problem.We can measure run-time by using a stop watch. But it’s not practical enough. Because we have to run the code all the time to measure the run-time.So the best solution is code analysis. We can measure the run-time just by looking at the code.

But the next question we come across would be,

“How to do code analyzing to check run-time?”

                   For that we use big O notation. Which is explained in the example below. 

Example 01 :

If there is an algorithm like below.

Capture

We put values to each statement like below.

Capture1

So the total run-time value is the sum of all the above values.

Which is,

Capture2

So in here ct1 and ct2 are numeric values.

The complexity of the above algorithm is O(n).

There are so many types of big O notations. N, n2, n3 are the most common types.

Below explains how we decide the complexity according to the big O notation

Capture3

When considering big o notation time changes according to the data input as the below diagram.

Capture4

As the n increases the time is also increasing gradually according to that. The following table explains the big o notations summary.

Big+O+Notation+Summary
Obtained by (http://donkcowan.com/blog/2013/5/11/big-o-notation)

written by Binu Senevirathne

Advertisements

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