How do you explain Big O in layman's terms in an interview?

Subscribe to my newsletter and never miss my upcoming articles

Say you order Harry Potter: Complete the 8-Film Collection [Blu-ray] from Amazon and download the same movie collection online at the same time. You're trying to test which method is faster. The delivery will take almost a day to arrive and the download will be completed about 30 minutes earlier. Great! Great! Great! So this is a tight race.

What if I order a few Blu-ray movies like The Lord of the Rings, Twilight, The Dark Knight Trilogy, etc. and download all the movies online at the same time? This time the delivery will still take a day to complete, but the online download will take 3 days to complete.

The number of purchased items (inputs) does not affect the time of delivery for online shopping. The output is consistent. We're calling this O (1).

For online downloading, the download time is directly proportional to the size of the movie file (input). We're calling this O (n).

We know from the experiments that online shopping is better than online downloading. It is very important to understand the big O notation because it helps you analyze the scalability and efficiency of algorithms.

Big-O is essentially measuring the rate-of-growth in time, for an algorithm, with reference to the size of input.

Analogy 2

Well, imagine that your pen is lost in a class of 'n' students. You decide to find the pen by asking the students in your classroom.

You can have 4 possibilities in the above situation:

O(1): You asked the first student to get your pen. It's DAMN! Was it pretty smooth right? This is O (1). It doesn't matter whether there are 10 or 10,000 students in the classroom. In your first attempt, you found it right, which remains constant.

O(n): Now, in the worst case, it could happen that you asked everyone in the class, and the last student you asked, got your pen. Well, that's O(n) because it depends on the class size. If you have 10 people in the class, you have to ask all 10 of them, if you have 10,000, you have to ask all 10,000 of them, so if you have 'n' students in the class, you have to ask all 'n' of them until you realise that the n^th person has your pen.

O(n^2): At one point in time, things are sure to get convoluted. Suppose you ask each student about the pen and tell him/her to ask the next student to send the message back to you. It will be much more intricate, and if there are 10 students, there will be 10^2(100) tryouts, for 10,000 students, there will be 10,000^2(Okay, do this math on your own) tryouts, and for 'n' students in the class it will be n^2 tryouts. This is O(n^2).

O(log n):This is more simplified than O(n^2). Imagine that you divide the class equally into two parts. If there are 10 students in the class, divide them into a group of 5 and ask each group separately. You've got to try 2 times this way (Either someone from the first group will have the pen or someone from the second group). This is O (log n). Here, technically, the log base doesn't matter, but you can generally think of it as base 2.

5 Big O run times sorted from fastest to slowest:

53.png

Sorting Algorithms Animations

The following animations illustrate how effectively data sets from different starting points can be sorted using different algorithms.

Heap Sort VS Merge Sort

Conclusion

  • The speed of the algorithm is not measured in seconds, but in the increase of the number of operations.

  • Instead, we're talking about how fast the algorithm's run time increases as the input size increases.

  • Run time algorithms is expressed in the Big O notation.

  • O(log n) is faster than O(n), but it's getting faster as the list of items you're looking for grows.

Now everyone has an idea about BIG O, if this article is helpful, please share and also subscribe to my newsletter to be notified when I post a new subject and also follow on

TWITTER

FACEBOOK

LINKEDIN

TUMBLR

Comments (3)

Gourav Khunger's photo

Very realistic analogies! Thanks for such a cool explanation... Also, can you tell me how you made those animations. They are awesome!!! 🔥🔥

Sandeep Bonagiri's photo

Hi Gourav, I am glad that you liked my explanation and its motivates me write more. Regarding those animations, I did that via CSS 3, JS and HTML with help of my friends

Gourav Khunger's photo

That's amazing! Keep up the good work Sandeep Bonagiri 😀