Big O Notation (Intro)

I heard this notation while I’m reading the Google Interview Question after I am received an e-mail from Google that my internship application getting noticed to them. Sometimes, it’s called Big Oh Notation. After reading some article, I’m getting understand what it’s use for.

How efficient is an algorithm?

That’s exactly what the statement that should keep in our minds about the Big O Notation. Let me give an example for you. Let we take one of the basic sorting algorithm, is Bubble Sort. If the item on the right is the smaller than the item on the left, then swap the position. So, the item on the right is larger than the item on the left. That is Bubble Sort. Look at the example below.

This is a jumbled number that need to be placed on the right order. The method that implemented at this kind of sort is comparing the two neighboring items. Okay, let’s finish it. The first step is comparing the first two items (first pass). The first item is 3, and the second item is 4. Which one is the smallest? The answer is 3, the left item. So, if the left item is smaller than the right item, we don’t have to do something to this condition. It’s mean, no swap required.

Then, we comparing the second item and the third item. Is that the left item, 4 is smaller than the right item, 5? Yes! So, no swap required.

Next, is that 2 bigger than 5? No, so we swap them.

The final step on the first step, is that 5 smaller than 1? No, so we swap them.

Hurray! The first pass finished! But wait, there is 4 more pass’ to finish. The next pass I will just show the figure without any explanation because the explanation main point is the same with the explanation above, right? ^^

Pass 2

Pass 3

Pass 4

Okey, the jumbled number has take the right position. So we called it now, the sequential number from 1 to 5. But, the system will not stop until all of the pass finished well, although the jumbled number has become a sequential. This is the only way the system know that the number has sorted well, especially if we are using Bubble Sort. Ok, next.

Pass 5

Haaa, finish! The number has been sorted well. Agree with me? ^^
But what do you think about that kind of sort? It will be not very efficient if the algorithm must sorting the large number of items. Bubble Sort is just efficient to the tiny number of items.

The Bubble Sort take n2 to complete, where n is the number of items in the list. Don’t believe that? Just count the number of the figure above, minus 1 (the original figure didn’t need to count). The notation should be like this: O(n2). That’s the worst case scenario. It can be optimized by, detect if any of the pass has been well sorted the list, then stop it. The notation for the best case is: O(n). This only required pass through the list once, and finish. That’s mean, the number of the list has been sorted.

Okay, that’s it. I need to improve the knowledge of this notation. If there is any reader that master already at this notation, please can you let me share the knowledge each other. ^^ … Thanks for reading! 🙂

NB: To watch the visual-demonstration of the step, click here.

2 thoughts on “Big O Notation (Intro)

Leave a Reply

Your email address will not be published. Required fields are marked *