Time Complexity and Big O Notation
Either you can download the notes in pdf (Link is given below) or you can read them on this site itself.
Time Complexity & Big O Notation:
This morning I wanted to eat some Pizzas; So, I asked my brother to get me some from Dominos (3 km far).
He got me the pizza and I was happy only to realize it was too less 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 is the study of the efficiency of algorithms.
Consider two developers who created an algorithm to sort n numbers. Shubham and Rohan did this independently.
When ran for input size n, the following results were recorded.
We can see that initially, Shubham’s algorithm was shining for smaller input but as the number of elements increases Rohan’s algorithm looks good.
Quick Quiz: Who’s algorithm is better?
Time Complexity: Sending GTA 5 to a friend
Let us say you have a friend living 5 km away from your place. You want to send him a game.
Final exams are over and you want him to get this 60 GB file from you. How will you send it to him?
Note that both of you are using JIO 4G with a 1 Gb/day data limit.
The best way to send him the game is by delivering it to his house. Copy the game to a hard-disk and send it.
Will you do the same for sending the game like minesweeper which is in KBS of size? No, because you can easily send it via the internet.
As the file size grows, time taken by online sending increases linearly – O(n’)
As the file size grows, time taken by physical sending remains constant. O(n0) or O(1).
Calculating Order in terms of Input Size:
In order to calculate the order, the most impactful term containing n is taken into account. (Here n refers to Size of input)
Let us assume that formula of an algorithm in terms of input size n looks like this:
Note that these are the formulas for the time taken by them.
Visualizing Big O:
If we were to plot O(1) and O(n) on a graph, they will look something like this:
Either you can download the notes in pdf (Link is given below) or you can read them on this site itself.
Time Complexity & Big O Notation:
This morning I wanted to eat some Pizzas; So, I asked my brother to get me some from Dominos (3 km far).
He got me the pizza and I was happy only to realize it was too less 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 is the study of the efficiency of algorithms.
Consider two developers who created an algorithm to sort n numbers. Shubham and Rohan did this independently.
When ran for input size n, the following results were recorded.
We can see that initially, Shubham’s algorithm was shining for smaller input but as the number of elements increases Rohan’s algorithm looks good.
Quick Quiz: Who’s algorithm is better?
Time Complexity: Sending GTA 5 to a friend
Let us say you have a friend living 5 km away from your place. You want to send him a game.
Final exams are over and you want him to get this 60 GB file from you. How will you send it to him?
Note that both of you are using JIO 4G with a 1 Gb/day data limit.
The best way to send him the game is by delivering it to his house. Copy the game to a hard-disk and send it.
Will you do the same for sending the game like minesweeper which is in KBS of size? No, because you can easily send it via the internet.
As the file size grows, time taken by online sending increases linearly – O(n’)
As the file size grows, time taken by physical sending remains constant. O(n0) or O(1).
Calculating Order in terms of Input Size:
In order to calculate the order, the most impactful term containing n is taken into account. (Here n refers to Size of input)
Let us assume that formula of an algorithm in terms of input size n looks like this:
Note that these are the formulas for the time taken by them.
Visualizing Big O:
If we were to plot O(1) and O(n) on a graph, they will look something like this:
