Course Content

Time Complexity and Big O Notation (with notes)

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.

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?

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:

 

You can download the notes by simply clicking on this below download link. :)

Download Notes here

Comments(2)

CoderZ 1 month, 3 weeks ago
https://bit.ly/316Fe7m
CoderZ 1 month, 3 weeks ago
https://bit.ly/316Fe7m

Resources

  1. Time Complexity - Download here

Course Announcements

Any Course related announcements will be posted here