Either you can download the notes in pdf (Link is given below) or you can read them on this site itself.
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.
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.
No. of elements (n) |
Shubham’s Algo |
Rohan’s Algo |
10 elements |
90 ms |
122 ms |
70 elements |
110 ms |
124 ms |
110 elements |
180 ms |
131 ms |
1000 elements |
2s |
800 ms |
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?
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(n^{0}) or O(1).
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.
If we were to plot O(1) and O(n) on a graph, they will look something like this:
You can download the notes by simply clicking on this below download link. :)
https://bit.ly/316Fe7m
Any Course related announcements will be posted here