Time Complexity and Big O Notation (with notes)

Summary

The video script narrates a relatable story to explain the concept of time complexity in computer algorithms. It compares two methods of obtaining a game—via internet download and physical transportation—to illustrate how different algorithms perform with varying input sizes. The analogy of file transfer speeds and physical travel time is used to distinguish between linear (Big O of n) and constant time complexities (Big O of 1). The script also emphasizes the importance of algorithm analysis, especially when scaling to larger inputs, and provides a visual representation of different Big O notations to help viewers understand their relative efficiencies.

Takeaways

• 😀 The story of being bored and wanting to play a game serves as an analogy for discussing algorithm efficiency and time complexity.
• 🚀 The script introduces two scenarios: downloading a large game (60GB) using limited internet bandwidth (1GB/day) versus physically transporting the game from a friend's house.
• 🔍 The importance of analyzing algorithms based on input size and the corresponding runtime is emphasized, highlighting the need to choose the most efficient method for a given problem.
• 📚 The concept of Big O notation is introduced as a way to express the time complexity of an algorithm, indicating how the runtime grows with the size of the input.
• 🛣️ The difference between the mathematical definition and the industry definition of Big O notation is explained, with the industry definition focusing on the most impactful term.
• 📈 The script uses graphs to illustrate how algorithms with different time complexities (e.g., Big O of 1 and Big O of n) behave as input size increases.
• 📝 The process of determining the time complexity of an algorithm is outlined, including identifying the highest order term and disregarding constants and lower-order terms.
• 🏁 The significance of understanding time complexity for real-world applications, such as sorting large datasets, is discussed, showing how different algorithms may be more efficient under different conditions.
• 📊 A visual comparison of various Big O complexities on a graph is presented, with green indicating more efficient algorithms and red indicating less efficient ones.
• 📚 The speaker provides notes and resources, such as Ds0.pdf and Ds1.pdf, to further aid understanding of time complexity and Big O notation.
• 🎓 The script concludes by encouraging viewers to review the material, like the video, and subscribe to the playlist for further learning on data structures and algorithms.

Q & A

What is the main theme of the video script?

The main theme of the video script is to explain the concept of time complexity and Big O notation in algorithms using a relatable story about choosing between downloading a game over the internet or physically going to a friend's house to get it.

Why does the storyteller decide to go to his friend's house to get the game instead of downloading it?

The storyteller decides to go to his friend's house to get the game because he has a limited internet speed of 1GB per day, which is insufficient for downloading large game files like GTA5, which is 60GB in size.

What is the significance of the 250kb game size mentioned in the story?

The 250kb game size is used as an example to illustrate a scenario where downloading the game over the internet would be faster and more convenient than making a physical trip, as the file size is small enough to be quickly downloaded within the 1GB daily limit.

What does the storyteller mean by 'algorithm 1' and 'algorithm 2'?

In the context of the story, 'algorithm 1' refers to the method of downloading the game over the internet, while 'algorithm 2' refers to physically going to the friend's house to get the game. These terms are used to draw a parallel with different approaches to solving a problem in computer algorithms.

What is the 'runtime' of an algorithm as discussed in the script?

The 'runtime' of an algorithm, as discussed in the script, refers to the time it takes for an algorithm to execute or complete its task. It is compared in the context of the two different methods of obtaining the game file.

Why does the storyteller emphasize the importance of analyzing algorithms before using them?

The storyteller emphasizes the importance of analyzing algorithms to determine their efficiency and suitability for a given task, especially considering how the runtime of the algorithm scales with the size of the input data.

What is the 'Big O' notation and why is it significant in the script?

The 'Big O' notation is a symbolic way to express the upper bound of the time complexity of an algorithm, indicating how the runtime grows as the input size increases. It is significant in the script as it helps to compare and understand the efficiency of different algorithms.

What does the storyteller mean by 'constant time' in the context of algorithm analysis?

In the context of algorithm analysis, 'constant time' refers to the runtime of an algorithm that does not change with the size of the input data. The storyteller uses this term to describe the time it takes to physically get the game from the friend's house, regardless of the file size.

How does the storyteller use the pizza example to explain time complexity?

The storyteller uses the pizza example to illustrate how the time it takes to get pizzas (the output) is affected by the number of pizzas ordered (the input size). This example helps to demonstrate the concept of time complexity in a real-world scenario.

What is the conclusion the storyteller draws about choosing the right algorithm based on the size of the input?

The storyteller concludes that the choice of algorithm depends on the size of the input data. For small inputs, one algorithm might be more efficient, while for larger inputs, a different algorithm might perform better. This is demonstrated through the sorting example with Shubham and Rohan's algorithms.

Outlines

00:00

🎮 The Dilemma of Game Acquisition

The speaker begins with a personal anecdote about the boredom experienced at home and the desire for entertainment. They mention a friend, Shubham, who lives 5km away and possesses a collection of games like Pubg and GTA5. The dilemma arises from the limited internet data available (1GB per day on Jio), which makes downloading large games impractical. The proposed solution is to physically visit the friend's house to copy the game using a hard disk, highlighting the trade-off between internet limitations and physical effort for immediate entertainment satisfaction.

05:00

🔍 Analyzing Algorithmic Efficiency Through Analogy

The narrative shifts to a discussion on algorithm efficiency by drawing a parallel between the game acquisition story and algorithmic problem-solving. The speaker explores the concept of time complexity in algorithms, using the example of transferring a small 250kb game versus a large 60GB game. They explain how the choice of method (internet vs. physical visit) is akin to selecting an algorithm based on input size, and how this choice affects the 'runtime' or time required to achieve the desired outcome. The speaker emphasizes the importance of understanding time complexity and choosing the most efficient algorithm as input size increases.

10:02

📈 Understanding Time Complexity with Real-World Examples

This paragraph delves deeper into time complexity analysis, contrasting two hypothetical algorithms for transferring data, represented by the internet method and a physical visit. The speaker uses the constant time of a physical visit (ignoring copying time) and compares it with the variable time of an internet transfer, which scales with the size of the data. The concept of Big O notation is introduced to describe the time complexity of algorithms, with the physical visit being O(1) and the internet transfer being O(n), where n is the size of the input. The speaker encourages the audience to consider the best algorithm based on the input size and to analyze algorithms for their time complexity.

15:02

📚 The Importance of Time Complexity Analysis

The speaker underscores the significance of time complexity analysis in algorithm selection, using the previous examples to illustrate how different algorithms perform under varying input sizes. They discuss the importance of understanding how the runtime of an algorithm changes with input size and the need to ask critical questions about the efficiency of an algorithm before its implementation. The speaker also introduces the concept of Big O notation in both its mathematical and industrial definitions, explaining the difference between the two and emphasizing the need to know both for academic and professional purposes.

20:03

📈 Visualizing Algorithm Performance with Graphs

The speaker discusses the visualization of algorithm performance through graphs, using the examples of Big O of 1 (constant time) and Big O of n (linear time) algorithms. They describe a scenario where the time required for a physical visit (constant time) and the time required for an internet transfer (linear time) intersect, indicating a point at which one algorithm may become more efficient than the other as input size increases. The speaker also mentions the importance of understanding different Big O notations and how they can be compared visually to make informed decisions about algorithm selection.

25:05

🍕 Practical Examples of Time Complexity in Daily Life

In this paragraph, the speaker brings the concept of time complexity into everyday life with an example involving ordering pizzas for a group of friends. They explain how the time it takes to receive the pizzas can be affected by the number of pizzas ordered, similar to how algorithm runtime is affected by input size. The speaker then transitions to a real-world example of sorting algorithms, where two developers' sorting algorithms are tested with different input sizes, demonstrating how an algorithm that performs well with small inputs may not be the best choice for larger datasets.

30:06

📘 Summarizing Time Complexity Analysis

The speaker concludes the discussion by summarizing the key points about time complexity analysis. They emphasize the importance of understanding the relationship between input size and runtime, and how to identify the best algorithm for a given task based on this relationship. The speaker also provides a visual chart comparing different Big O notations and their performance, encouraging the audience to review the provided notes for a deeper understanding of the concepts discussed in the video.

Keywords

💡Algorithm

An algorithm is a set of rules or steps used to solve a problem or perform a computation. In the context of the video, the term is used to describe different methods for transferring a game file, illustrating how the choice of algorithm can affect the efficiency and runtime depending on the size of the input, which in this case is the file size.

💡Input Size

Input size refers to the amount of data that an algorithm processes. The video uses the analogy of file sizes to explain how the input size can influence the performance of an algorithm. As the input size increases, the runtime of certain algorithms may increase at different rates, which is a key concept in analyzing algorithm efficiency.

💡Runtime

Runtime is the duration it takes for an algorithm to complete its task. The video script discusses how runtime changes with different algorithms as the input size varies. For instance, the runtime for an algorithm that copies a game file over the internet increases with the file size, whereas the runtime for physically transporting a game on a hard disk remains constant.

💡Time Complexity

Time complexity is a measure of how the runtime of an algorithm grows with the size of the input. The video explains time complexity through the lens of two different 'algorithms' for acquiring a game, emphasizing that as the input size (game file size) increases, the time complexity of the internet transfer algorithm is linear (Big O of n), while the physical transfer has a constant time complexity (Big O of 1).

💡Big O Notation

Big O notation is a symbolic way to express the upper bound of the time complexity of an algorithm. The video script uses Big O notation to classify and compare the efficiency of different algorithms. For example, an algorithm with a time complexity of Big O of n is said to run in linear time, while an algorithm with Big O of 1 has a constant runtime, regardless of input size.

💡Constant Time

Constant time refers to an algorithm's runtime that does not change with the size of the input. In the video, the physical visit to copy a game file is described as having a constant time complexity, meaning the time taken is the same whether the file is small or large.

💡Linear Time

Linear time indicates that the runtime of an algorithm is directly proportional to the size of the input. The video uses the example of transferring a game file over the internet to illustrate an algorithm with linear time complexity, where the time taken increases as the file size grows.

💡Internet Speed

Internet speed is the rate at which data is transferred over the internet. The script mentions internet speed as a factor affecting the time it takes to transfer a game file online, with the speed being a constant (L2) in the example used to calculate the time complexity of the internet transfer algorithm.

💡Physical Visit

A physical visit, in the context of the video, refers to the act of going to a friend's house to copy a game file onto a hard disk. The video contrasts the time complexity of a physical visit (Big O of 1, constant time) with that of an internet transfer (Big O of n, linear time) to demonstrate different algorithmic efficiencies.

💡Efficiency

Efficiency in algorithms refers to how well an algorithm performs in terms of time and resources used. The video script discusses the efficiency of different methods for transferring a game file by comparing their time complexities, highlighting that the choice of method can greatly affect efficiency based on the input size.

Highlights

The story analogy used to explain the concept of choosing between different algorithms based on input size.

The importance of analyzing algorithms based on their time complexity as the input size increases.

The introduction of two hypothetical algorithms, Algorithm 1 for internet file transfer and Algorithm 2 for physical file transfer.

The concept that Algorithm 1's runtime increases linearly with file size, while Algorithm 2 remains constant regardless of file size.

The practical example of choosing between downloading a small game versus physically visiting a friend to get a larger game.

The mathematical representation of algorithms' runtime, emphasizing the highest degree term in the equation.

The explanation of Big O notation as a measure of an algorithm's scalability and efficiency.

The difference between the mathematical and industrial definitions of Big O notation.

The graphical representation of algorithms' runtime, illustrating the difference between constant time and linear time complexity.

The real-world example of pizza delivery to demonstrate the impact of input size on the time required for task completion.

The use of sorting algorithms as a practical example to compare the efficiency of different algorithms with varying input sizes.

The importance of choosing the right algorithm based on the expected input size for optimal performance.

The detailed explanation of how to calculate and understand time complexity using Big O notation.

The significance of the highest order term in determining the time complexity of an algorithm.

The visualization of various Big O complexities on a graph to compare their performance as input size grows.

The guidance on how to approach the study of algorithms and time complexity for better understanding and application.

The encouragement for viewers to revisit the material if they did not understand it the first time, emphasizing the importance of grasping these concepts.

The conclusion that highlights the value of the video in teaching the concepts of time complexity and Big O notation.

Transcripts

I want to tell you guys one story.

It happened like this, I was bored in my house.

What was happening? I was bored. This is my house.

This is me.

What was happening in my house? I was getting bored.

I have a friend who stays 5km away.

And 5kms away,

Let's assume that friend's name, shubham ok.

And this friend stays 5km away.

Listen carefully,

Now what happened, I was getting bored a lot.

I was so bored that I needed some entertainment.

This guy has amazing games like Pubg and GTA5.

So he has a collection of games. He likes playing games a lot.

And you can get every type of game from him.

But there is one problem,

I also use jio.

He also uses jio. What does he use? He also uses jio.

We get 1Gb. We get just 1 Gb for one day.

And we are not much into broadband internet.

And with more internet, we can't sell files and all.

So if I have to take the game from him,

So for me, what is the fastest way?

If I want to play that game now itself.

So what is the fastest way for me,

To take the game from this friend.

Tell me that,

So you will say there is nothing to doubt in this,

Take a hard disk, copy it, and bring.

So what will I do?

I will take my bike and bring that game by bike.

So this is me, I am going through the bike.

I will go and bring that game.

And I will enjoy the game and satisfy my soul.

Ok, this is done, but why am I telling this story to you guys?

If I say that game is 250kb

There is one simple game of 250kb.

Then will I go to his house and bring it with the hard disk?

Tell me, no right?

I will tell him to add it to the drive,

Or email it or upload it somewhere.

I will tell him to upload it anywhere.

There is dropbox, there is Gmail's google drive

In Gmail also 250kb can come.

There are many ways even you know it.

Now, over here

Tell me one thing, if I ask you one question,

What is the size?

When you need to change your way.

To get the game.

To get the game.

Now look,

What way did you take to get the 250kb game?

You used the internet.

Because for you it was fast.

And for 60 GB what did you take?

For 60 GB you took a physical visit.

You applied it because if you will visit physically,

So quickly I will bring my game to the hard disk.

Internet is 1GB per day.

How will 60 GB come? ok.

So you used this.

If I question you,

As the size of this input will get increased

Consider this as an input, now let's move towards technical terms.

Enough of analogy, Enough of stories.

This is input.

And what is the output?

Output is you have to bring it.

What do you have to achieve?

What is your problem? You need a game.

You have to solve the problem.

Consider this as an algorithm.

Consider this algorithm 1 and this one as algorithm 2.

Ok

Algorithm 1,

You applied that for 250kb input.

You used algorithm 2 for 60 GB input.

This means that,

As the size of the input was increased

Like that, the runtime of the algorithms

Do you understand runtime?

The time you required to bring it.

Understand that.

In that much time, the runtime of the algorithms keeps on changing.

As the input will keep on increasing

The runtime of those algorithms will increase.

Let us analyze if it is true or not.

If I am sending with through the internet,

If I am sending 230kb

Consider it comes in 2 sec ok.

Maybe if I send 1 MB

Then in how much time it will arrive?

Here 250 kb, I will keep things very simple.

Consider 250 kbps speed ok

Kbps speed is coming and you sent

250 kb then it came in 2 sec ok.

And if you sent 1 MB then you will need 4 secs.

So if your file is 250 kb

Then it needs 1 sec and if the file is of 1MB

Then you will need 4 secs ok.

It means that as the input size is increasing like that

The time required to send the file,

That is also increasing.

So here its runtime is changing,

Along with input size.

Will this also change its runtime along with input time?

There is a hard disk then there is your motorcycle.

You will go on that bike.

And you will take it and in hard disk whether you bring 250kb

Or after that you bring Tb

Assuming we will ignore the copying time.

Copying time is negligible.

So if you will go and bring it then you will require the same time.

It is the correct thing & let's assume you call your friend

That copy it and keep it ready, I am coming.

So that time we will consider a constant ok

That time won't be required.

Then what will happen?

After increasing your input there was no change in your runtime

Ok

So as the input size of algo2 increased

Like that what happened?

For that, there was no change in the runtime.

Runtime remained the same.

So you will say what is this?

Ok, so both of them are different algorithms.

And of these both algorithms

We are to trying to remove the time complexity of them.

When we ask questions like as the input will increase,

Then the runtime will change as per what?

According to what? Take a guess at it.

Now, maybe I take to you copy 5-6TB

Then you will forget by the internet.

If you have a NASA internet connection then it is ok,

But if you jio then go sleep.

Don't sleep just forget about the file.

It won't come.

It won't go.

From your friend, it won't come to you ok.

It will take so much time.

So when we analyze algorithms

Before using any algorithm we analyze it

And we ask questions to ourselves

Is it the best algorithm for me?

And is there any other algorithm that performs better?

So from where do, we take the father of good?

So we say as the size of the input keeps on increasing,

Similarly, what is the effect of the algorithm on runtime

We ask for the answer to this question

And asking the answer to this question is called analysis

Time complexity analysis.

In these two algorithm,

You tell me if overall I need time

If I say algo 1 time ok

I will do one thing, I will go mathematical

And here I will write T algo 1

I will say that you have to make a formula.

Ok, you have to make a formula.

That will denote T algo 1.

Now, consider you need K1 secs to change clothes.

Ok

Because we have to go to friend's house,

If you will wear dirty clothes what will aunty say?

What are you wearing?

You need to get ready and make hair and all.

So you need k1 time for that.

Now consider your vehicle your bike,

And the time required to reach the friend's house

That is k2 ok.

And after that

Now you will go to aunty's house

You will be treated.

Aunty will make some tea and all.

So consider you need K3 time in that.

Now, you will go and his father will ask you

Does he come to school or not? Does he bunk the college?

How is he? Does he get scolded?

So consider for all this K3 time is needed.

And after that, you came back in k4 time.

Consider there are different routes to come and go.

Whatever

So does it depend on the time

On the size of the input

If I consider the size of input as n

What is n? It is the size of the game.

N is game size. Size of game.

Which you are going to bring.

Now here if you add 10Gb

Or here if you add 100Gb

Or you add 2Tb. You will copy and bring it.

In that much time.

Now, if I say write it in n terms.

You will say we can't write in n terms as constant time is required

I will say write it.

You will say, how are you behaving harry.

If it can't be written then how will I write it?

Now, if I stand on your head and say no write it.

Or else it won't be good.

Then you will say if you are insisting then take it.

K1 n to the power 0+k2+k3+k4

Even I am happy and you are happy as always.

Ok, K1 n to the power 0

N to the power 0 is 1.

So what did I do?

I wrote it in n terms. Now, listen carefully to this,

Now, I am telling about Big O.

What is Big O?

Now here forget Big O. Forget what is Big O.

Remove your brain from all these things,

Just understand what I am saying.

Here you are understanding a story. we are listening to a story.

We are not studying algorithms

Let's assume we are listening to a story.

We are doing a real-world analysis of things.

T algo 1

If I write in n terms, time taken by algo 1

I think it should be algo 2, I am sorry it's algo 2

Because the physical visit was algo 2. no worries.

Algo 2 is a physical visit.

So let me correct,

This time is required in algo 2.

So algo does not depend

Now, if I say in these 4 terms

Which term can make it big?

Biggest

You will say n to the power 0 in all these, so n to the power 0.

So this is Big O of n to power 0.

Because what was the most impactful term in n

It was n to the power 0.

And so I said bigger n to the power 0.

What is the n to the power 0?

Why complicate things?

When we can write n to power 0 as 1.

So this is Big O of 1 ok.

So this is the algorithm that runs in constant time.

Big O is called a constant runtime algorithm

Because it was constant.

Because it was constant we remove n to power 0 and make it 1.

So Big O of 1,

Run time of it, there are some things that we will recite.

Because we won't constantly use our brains again and again.

As we see Big O of 1 it is constant.

We have to declare it constant.

Now, come here and listen to another story.

Now, look what is here?

If we do an analysis of the first algorithm

If I do T algo1

Then what will happen here?

What do I have to do? I have to upload it.

When I am sending data, then I have to upload and send.

My main time is required in that ok.

Now, considering I turn on my computer

In that, I will need time L1

After that what happened?

Consider all preparation I required L1 which will be a constant

5 secs,2 secs, 10 secs

If there is an SSD in your computer then it will open in 4 secs.

If you are using a supercomputer then it can even open in 1 sec.

L1+ consider your speed is L2.

Ok, so it takes a constant speed of your connection

Which is not present in jio,

Ok, but let's consider it is constant ok.

Your internet speed is L2 Kbps ok.

Ok, so id L2 kbps is your speed

Where should I write? I will write here.

L2 Kb per sec is your speed.

And along with consider that game is of L3 kb.

Ok

Sorry L3 is not kb, game is of n.

L is the size of the game.

Consider that game is of N kb.

Then what will you do?

If the game is of N kb then how much time will you need?

You will require n/L2

Ok, so n/L2

Speed= distance /time

You have studied simple physics. What should I teach you?

Ok, so here we removed the distance.

Sorry, we used distance and speed to calculate time.

That is how much time will be required.

If I use my algo 1.

Which means the internet way.

So I will divide it by my internet speed.

Ok, so the speed is distance/time.

And time= distance /speed.

So my distance,

I divided my size by game.

Ok, n/L2.

Now here can I consider 1/L2 as another constant?

Consider L2'

Just to simplify a little bit.

Ok, so what did I do? I considered that

My this 1/L2

It is another constant that I called L2'

And after calling it L2'

I will write it like this.

L1 n0+ L2' n1

Now tell me which is the most impactful term in these both?

Among these two.

Obviously, it is this.

And what is its degree? What will it be if we remove constant

N to the power 1.

And I will write it like this.

This is not equal to. Writing equal to is wrong here.

So here I will add one tilt.

Approximately I will say that

The most difference that will be visible

It will be because of this term.

Compared to this term.

Because n to power 1, if I increase input and make it 10 lakh

So this was of 2 lines but this will become 10 lakh.

So the higher degree term in the polynomial

In any equation

The most impactful term

It is taken ok.

So I picked it over here.

I picked this because in the comparison with n to the power 0 it is big.

And I want to see things in a simple way.

I want to simplify ok.

Now, I will write this as

Big O of n to the power 1, that means Big O of n.

So this algorithm is big O of n.

Which means it runs in linear time.

I will call it linear b.

Ok, if you go into the real world or industry

You get a job in any product-based company

Then what will happen? There you won't listen to a story.

You will be given an algorithm and input.

And accoring to that,

You have to realize In how much time you will get the output.

You have to choose the algorithm according to yourself.

So I have made nodes

That is amazing, we will see one more example.

But before that, I want to understand this thing.

And this thing is very basic.

And it makes a foundation of algorithms.

It is very important I want to tell you that.

It is very important, so understand it very carefully.

I have tried to simplify it.

Even now if you haven't understood then the reason is

While watching the video you were not paying attention.

You can go back and watch it again.

There is nothing wrong with it, go back if you haven't understood.

I don't recommend moving forward if you haven't understood.

From where you haven't understood watch it from there.

It is a simple story ok.

You can send file by internet or can physically go and copy in hard disk.

If you will send with the internet,

The time required will be dependent on the size of the file.

If you do a physical visit,

Then the time required will be as per the size, The time required will be constant.

So I told you how I wrote constant as Big O of 1.

How I wrote this as Big O of n.

I told you that.

Now there are many types of algorithms

Like Big O of n of n.

Now what this log is, we will talk about it later.

Big O of n square.

And Big O of n cube.

There is also Big O of factorial n.

So we will see all that things.

But here I just want to tell you,

Linearly if your time

Is scaling with the input size,

Big O of n.

And if it is constant then Big O of 1 ok.

So time complexity analysis of Big O tells that

That your time, the time that is required

To run your algorithm

It scales according to what?

If it runs in linear time

Big O of n.

If it runs in constant time,

Big O of 1 ok.

So here this thing is clear.

I hope it is cleared.

I will quickly clean the board.

So I have kept this duster properly.

And it gives me a lot of convience.

Now, we will put some light on Big O.

What is this Big O?

What have I written this O O?

Ok, I will explain this now.

And this thing is very necessary so listen carefully.

You will have questions about it, so further we will do questions of Big O.

Then question will become a game of your fingers.

Of fingers.

That too of reverse hand fingers.

I have to adjust this like this.

Just it does not fall, No it won't fall.

It is a good kid. Now, what we will do over here?

We will understand what is Big O?

Now, look the mathematical definition of big O is different.

And Big O's industry definition is different.

And this thing,

I will tell you one is the mathematical definition.

And one is the industrial definition.

It will be asked in the industry ok.

So what will happen in the industrial definition?

You have to precisely tell what is Big O.

And here I will also call it the order of.

So further we will learn Big O, big omega and big thita.

But now just understand that,

O in the industry means the order of

And its mathematical definition that I will tell you

We will see it further.

But I want to put this thing in your mind

If we define Big O in mathematics.

Then it is slightly different

As the industry person will take your interview

He will ask or else if you are giving exams like GATE and all

By the way, you can watch this course for GATE.

There is no problem.

Here I told you I am making it for placement preparation primarily

But it does not mean you can't watch it for GATE.

All concepts are the same.

When you are solving a question then there is the mathematical definition.

But when you are answering in industry

Then industry definition is used.

What is the difference between both of them?

The big O of n

It is automatically big O of n square ok.

And that automatically is also big O of n cube.

So write higher-order terms like this.

This is its mathematical definition.

But your industry definition expects that

Write it in as smaller as you can.

Ok, so here

Industry definition is a minimum of this.

You will have to analyze the outcome and write the minimum.

Now, further, we will see what is its value.

Further, we will see what mathematics is involved in it.

Why does it happen?

But now if you find this thing strange

Leave it, we will see it further.

But I just wanted to tell you ok.

So when I use its mathematical definition then I say Big O

But when I give industry definition

Or I am answering any interview.

Then I will say an order of.

I will say the order of because big O has a different definition.

But they are used interchangeably.

But you should know the story. This is a storyline.

What is in industry and what is its mathematical definition?

Here it is used in a different way.

So you should know that thing. Ok.

So quickly I will erase it.

And along with that what will I do?

I will make a graph. A graph is very important.

Where is my duster? It is up.

Previously I use to keep it there.

Now I will erase it.

Now what we will do?

We will make a graph ok.

So you saw two algorithms.

Our algo 1

Please stay here.

Our algo 1

That was we will send the file through the internet.

And our algo 2

It was a physical visit. I will write it as PV.

It is not an IIT's question PV.

It is a physical visit ok.

So here what am I doing?

Algo 1 is the internet.

And we saw that this is Big O of n.

And this was Big O of 1.

It was a constant time run algorithm ok.

Now listen to me very carefully.

If I say,

That I want to plot.

Input and time.

What is this time? It is the time at which you reached your friend's house.

And what is this n?

This is the n

What is this? It is the size of the game.

It is your game size ok.

So it is game size.

So if I plot algo 2 then this was constant.

Every said K1+

You watch it.

Go back in the video, I wrote the equation over here.

Whatever it is constant, its graph will be plotted like this.

So Big O of 1 is plotted like this.

It does not mean it is 1's graph.

Don't confuse it with the x=1 graph.

This is the graph of x=k.

Constant, whatever constant was there in constant time it was running.

And whose graph is this that I am making? It is a graph of Big O of n.

And this y=mx+c

It can be somewhat distorted.

We have just taken higher-order term ok.

So what is it? It is the graph of Big O of n.

Consider, when you wanted to send 250kb

So when you wanted to send a 250 kb file

Then where did you need less time?

Here is less time.

Clearly in Big O of n.

You were sending it through the internet.

Then as your file size was increasing,

Then it became difficult for you to take a decision.

Can I send it?

Can I send it or not?

Then here there will be one such time, consider that

I will consider 1 Gb ok.

That is 1 Gb you need that much time only.

Let's consider. Let's assume it's ok.

That you require the same time in 1GB as you needed in sending internet.

That much time you will need in the physical visit.

So at one time, they will meet Big O of 1 and Big O of n

And after that in Big O of 1, you will have a benefit.

Ok, as input size will increase.

So consider as the size of the game becomes 20GB

You won't want that you will have to wait for so much time.

You will want to go home and bring it.

So in that, you require less time.

So I made this graph of Big O of 1 and Big O of n.

It is not a graph of y=1 and y=n.

It is the graph of the Big O of 1 algorithms equation.

It is the graph of the Big O of n algorithms equation.

Ok,This y=1, y=n

Or else y= whatever equation was there of algorithm runtime

It is a graph of that approximately.

So we will approximately plot that.

And we will compare those all ok.

We will compare, so

I will also show you other graphs.

At this time I would like to take you,

Towards the notes that I have made for you all.

And let's see some concepts from it.

And let's try to understand this thing more.

So the notes I have prepared for you all,

You must be knowing the Ds0 pdf

I have already given that.

And the Ds1.pdf

I have said 0 to the introduction so it is Ds0 pdf.

And we will open Ds1.pdf and as you can see

I have opened Ds1.pdf

And along with that, I am giving you an example.

Of some pizzas

So here I have given an example of time complexity.

If I want to eat a pizza I can send my brother to bring pizza.

But my friends also come.

Here I have written you can read it,

Here I have written if some friends come to your house.

Then you can't order 68 pizzas at once.

It can't come in an optimal or short time.

Maybe he needs to do 10 rounds.

Or maybe he needs 15 rounds to bring it.

You got the point.

The size means the pizzas that you want to order,

It is affecting the time over here.

The time in which you get the pizzas.

It is affecting that.

As you saw over here.

So we saw time complexity over here.

So if I define time complexity,

Then that is the study of the efficiency of algorithms.

How time taken to execute an algorithm

Grows with the size of the input.

As the size of the input will increase,

In that way what will happen to time?

The size will increase and time will increase or decrease

So here I took an example,

Of two developers.

What are they doing?

They want to sort n numbers.

So here I am giving a real-world example because

The examples we took were very naive.

They were very simple.

Now, here I am taking a real-world example.

Of sorting of n numbers.

If of n numbers

N can be anything. It can be 10,20,100

I can make it 1000 numbers.

In sort, consider there is an element in an array.

There are elements in arrays.

I want to sort them.

So when I will run it for input size n,

So I told shubham to make an algorithm

And I told Rohan to make an algorithm.

And both made the algorithms.

And after that I tested them.

So the algorithm which was of shubham

To sort10 elements he took 90 milliseconds.

In 1 second there are 1000 milliseconds.

And Rohan's algorithm took 122 milliseconds.

So from here, I found that Rohan's algorithm is bad.

What are you doing? What have you written?

Then I gave 70 elements.

Again shubham's algorithm won.

I said Rohan you don't know how to code.

What have you written?

It is taking 124 ms to run. Learn something from shubham.

His algorithm runs in 110ms.

After that, it was time for 110 elements.

And over there shubham's algorithm took 180ms.

And over there Rohan's algorithm was around 120-130ms.

It took 121 ms.

After that when I gave 1000 elements for their algorithms,

Then shubham's algorithm got busted over there.

It took 2 seconds.

But Rohan's algorithm did it in 800 ms.

So what will you conclude from this?

Here you can see, initially, if we have to use for less elements

Then Shubham's algorithm is better.

But if I have to run for big elements

If I have to run on big data then I will use Rohan's only.

Even though it takes more time for short elements

In comparison to Shubham's algorithm.

Then here I have asked one question,

Whose algorithm is better?

Whose algorithm is better?

So here the answer is both are better in their places.

If I compare it overall then I will give it to Rohan.

The prize of writing a good algorithm.

As the size increases, he wrote as per that.

Shubham for the small elements,

Maybe he coded something for small elements.

Which can sort. Maybe I am just saying.

And the good algorithm runs in less time for big input.

Ok, so it is an identity of a good algorithm.

So here if we have to do small elements

Consider if I have to do for 10 or less than 10 elements,

Then I won't see Rohan's algorithm.

But if I need to sort big elements,

In general, if I have to plugin an algorithm in any system

Then I will plugin Rohan's algorithm

Because it optimally performs for big inputs too.

I don't want to read full notes.

I have written the same thing that I told you before.

Jio story which you must have seen.

And we saw as the file size was growing

The time for online sending was increasing.

Physical sending was happening in constant time.

Now, here I have explained properly how to calculate order time.

Here I told you the highest order term

That gives a big impact on the formula.

It gives a big impact,

That is n square ok.

Because if you add a big value of n,

Then this will be nothing in comparison to as big this will.

Put 10k value and see what is the value of this term.

This is a full overall term and overall equation

How much importance is it giving?

How much value it is adding?

So you will know this.

So we take the highest order term of this equation.

Not necessary it is the highest degree polynomial.

It is not necessary to be a polynomial.

In this equation, it can be factorial.

It can be anything, ok.

But we take the highest order term.

And after taking the highest order term,

What we will do? We will add in Big O.

And Big O n square is here.

And here n whatever it is,

Like here it was 5 size n.

In that term, we will write the equation.

After that, we will take the highest degree term.

As here we wrote Big O n to the power 0.

I did it Big O of 1 as n to the power 0 is 1.

Because there was no n in it. It was running in constant time.

So in this way we analyze algorithms.

Now, look over here

Note that these are the formulas for time taken by them.

Ok

These are the formulas.

Some constants are used, by removing some constants

You can pick the highest order term ok.

Then I visualized it for you guys.

And here I showed you guys that

How you can plot Big O of 1 and Big O of 1 in a graph?

And here we can also plot other algorithms.

Big O of 1, Big of n,

We can plot algorithms on one sheet.

And here I have added one thing over here

As I plotted and showed it to you,

On board that Big O of 1

And Big O of n can be plotted on the graph.

Here I have added a very beautiful chart.

In which Big O's are compared.

How will big O of log look in graph?

How will big O of 1 look?

This is Big 0 of n and Big O of n logn.

This is big O of n square.

This is Big O of 2 to power n.

This is Big O of factorial N.

And here they have also marked it with colors.

How does this algorithm go in a good and bad way?

Green means good and red means bad.

Bad as in it takes more time to run.

And I have taken it from stack overflow, you can go and check the answers.

But I got most of the value in this figure over here.

So I took this over here.

You can understand it properly just by looking at it.

Definitely read these notes once.

It is very important for you.

If you read notes along with the video.

Then I don't think you will have a problem understanding time complexity of Big O.

Now, in the next video,

In upcoming videos we will solve problems & see other concepts

But I hope this video added value.

If you think this video is good

If you liked it then do like this video.

Along with that if you haven't accessed the playlist

Of data structures and algorithms

Then definitely access it,

Because it is the place where everything is going to be uploaded.

This is the playlist, I will add everything here.

All videos will come in this.

If you bookmark it then it will be good for you.

By clicking here and here save it.

This much only for this video guys.

Thank you so much guys for watching this video.

And I will see you next time.