Time Complexity and Big O Notation

An analogy to a real-life issue:

• This morning I wanted to eat some pizza; So, I asked my brother to get me some from Dominos, which is 3 km away.
• He got me the pizza, and I was happy only to realize it was too little for 29 friends who came to my house for a surprise visit!
• My brother can get 2 pizzas for me on his bike, but pizza for 29 friends is too huge of an input for him, which he cannot handle.

What is Time Complexity?

Time Complexity measures how long an algorithm takes to process an input. It helps us understand the efficiency of an algorithm as the input size grows. For example, finding the largest number in a list takes more time as the list gets longer.

Consider two developers Shubham and Rohan, who created an algorithm to sort ‘n’ numbers independently. When I made the program run for some input size n, the following results were recorded:

We can see that at first, sijan's algorithm worked well with smaller inputs; however, as we increase the number of elements, bijay's algorithm performs much better.

Quiz Time: Who’s algorithm is better?

• Imagine you have a friend who lives 5 km away from you. You want to send him a game. Since the final exams are over and you want him to get this 60 GB file worth of game from you. How will you send it to him in the shortest time possible?
• Note that both of you are using 5G with a 5 Gb/day data limit.
• The best way would be to send him the game by delivering it to his house. Copy the game to a hard disk and make it reach him physically.
• Would you do the same for sending some small-sized game like MineSweeper which is in KBS of size? Of Course no, because you can now easily send it via the Internet.
• As the file size grows, the time taken to send the game online increases linearly – O(n) while the time taken by sending it physically remains constant. O(n0) or O(1).

Calculating Order in terms of Input Size:

In order to calculate the order(time complexity), the most impactful term containing n is taken into account (Here n refers to Size of input). And the rest of the smaller terms are ignored. Let us assume the following formula for the algorithms in terms of input size n:

Here, we ignored the smaller terms in algo 1 and carried the most impactful term, which was the square of the input size. Hence the time complexity became n^2. The second algorithm followed just a constant time complexity.

Note that these are the formulas for the time taken by their program.

What is a Big O? Simply put, in our industry, Big O represents the "order of" an algorithm's efficiency, but this is slightly different from its mathematical meaning. In math, Big O covers all possible complexities an algorithm could have, while in the industry, we focus on the worst-case or minimum complexity. This is a subtle yet important difference.

Visualizing Big O: If we were to plot O(1) and O(n) on a graph, they would look something like this:

So, this was the basics of time complexities. You don't have to worry about things passing you by. We’ll learn more deeply in the coming videos. For now, just stay with me.