We have seen that time complexity is expressed using the Big-O notation, and time complexity is nothing
but how runtime of an algorithm grows as the input grows.
Now let's say for an input size of n, we have found that the number of operations we have counted,
that the number of operations that the computer has to do is a function of n f of n.
Now, a quick side note over here.
What is a function?
If you're not aware of this, let's take a quick side note.
Let's say we have f of x is equal to x square plus one.
So over here we can say that this is a function of x.
So this means that if x is the input the output is f of x.
So when x is equal to one f of x becomes one square plus one which is two.
So when x is equal to two, the f output which is f of x becomes two square plus one which is five.
So this is what we call a function.
So let's get back over here.
Let's say for an input size of n the algorithm makes the computer do an f of n number of operations.
All right.
And again when we're doing the complexity analysis we are not interested in the precision or the details.
But we want to know the trend.
So basically we want to know as n increases what is the trend that the number of operations performs.
The number of operations or f of n is going to take.
So we want to know the trend of this.
So is it something like this or is it something like this?
Is it something like this?
Etc..
So we want to know about the trend.
All right.
So let's take a look at this.
So let me just make some space over here.
And for this to identify the trend we are going to make use of something called asymptotic analysis.
So let's try to first develop an intuition regarding what asymptotic analysis is.
Let's say we have found that f of n is equal to n plus three.
So when n is equal to one, the number of operations is required is one plus three, which is four.
But when n is equal to 1000, the number of operations is going to be 1000 plus three, which is 1003.
Now what happens when n becomes very large?
For example, 1 million or 1 billion?
In that case, you can see that this three over here becomes insignificant, right?
We just want the trend.
So whether we are getting a value 1,000,003 or 1 million, this over here makes no impact with respect
to the trend.
We are not interested in the details.
Therefore we can just avoid this so we can neglect this over here.
And if we found that f of n is equal to n, then we can say that the time complexity of this particular
algorithm is of the order of n or o of n.
So we are using the big O notation over here.
Now this implies that as the input size increases, the trend is such that the time taken or the number
of operations to be done is increasing linearly or in proportion to the input size increase.
So if you are going to plot this, this is going to be something like this, right?
So as n is increasing the number of operations which is on the y axis is also increasing in that same
proportion.
All right.
So this is an example.
So this over here indicates that the particular algorithm with which we are dealing with has a big O
of N or the time complexity is O of n.
Now let's take a look at what Wikipedia talks about asymptotic analysis.
Over here you can say that it says we are interested in the properties of a function f of n as n becomes
very large.
So that's the case over here right.
We want to see if the algorithm scales efficiently.
Now over here it says if f of n is equal to n square plus three n.
As n becomes very large, the term the term three n becomes insignificant compared to n square.
The function f of n is said to be asymptotically equivalent to n square as n tends to infinity.
So this is the same thing that we have seen previously.
Previously the function was n plus three, and as ten as n tends to infinity.
This became insignificant, and we can say that n plus three is asymptotically equivalent to n or we
wrote o of n as the time complexity of that particular algorithm.
Previously, when we identified f of n to be equal to n plus three, we said that as n became very large
or as n approaches infinity, this three over here became insignificant, and therefore we just have
n over here.
And hence the time complexity of this algorithm is of the order of n or o of n.
Now we have just now seen another example where f of n if that is equal to n square plus three n.
Now again, if n becomes very large, like something like a million when you compare these two terms
right this term over here, three n is going to be insignificant compared to n square.
Why is that.
So let's take n is equal to 1000.
So in this case n square becomes 1000 into 1000 which is a million right.
So this is a million.
And this over here is just 3000.
So when you're comparing 3000 and a million this is actually insignificant.
Again if you increase this to 10,000 again you can see that the difference is still starker.
All right.
So when n becomes very large and when n is tending towards infinity, this term over here is insignificant.
And then we are just left with n square.
So we can say that the time complexity of this algorithm, where the number of operations is n square
plus three n, is of the order of or big O of n square.
So you can see that we are using the Big-O notation to express the asymptotic analysis, which is nothing
but what the function becomes when n tends to infinity.
Now let's take a look at another example.
Let's say f of n is equal to two n square plus five n.
Now, because of this same reason over here, because this is insignificant compared to this, we can
eliminate this.
So five n can be eliminated.
And then we are left with two n square.
And we only want to know the trend.
Right.
Because his analysis only is interested in the trend.
Or we want to know how the algorithm, the number of operations that the algorithm has to do or the
runtime of the algorithm will increase as the input scales.
So we are only interested in the trend so we can get rid of this constant as well.
And we are just left with n square.
All right.
So we want to know in what proportion does the number of operations increase when the input size increases.
And we can say that the proportion of increase is going to be of the order of n square or O of n square.
So that's why we can say that the time.
Complexity of this algorithm.
If this is the relationship between the input size and the number of operations to be done, is going
to be O of n square.
So we have understood what asymptotic analysis is.
It's actually checking what the function becomes when n is tending to infinity or when n becomes very
large.
Let's now proceed to point number four, which is what is big O.
We have already seen that big O notation is used to express whatever we understand in the asymptotic
analysis.
Now if f of n is equal to five n plus three, if this function represents the relationship between the
input size, which is n, and the number of operations that the output that the algorithm has to do
to get the output.
In that case, we can avoid the constants, and we can say that the time complexity of this algorithm
is of the order of n.
All right.
Now, if the time complexity of an algorithm is of the order of n, what does this mean?
It means that the number of operations that the algorithm has to do is bounded by a multiple of n.
So it could be five n or 100 N or 1000 n.
It's a constant into n, and we are just avoiding the constant because we are only interested in the
trend and not the details.
So whenever we are talking about big O, remember another important thing to note is that we are always
talking about the upper bound or the worst case scenario.
So you can see that the number of operations is bounded by or the upper bound is going to be a multiple
of n.
If we have the time complexity for an algorithm to be O of n, and in most coding questions, we don't
need to be considered by this, because in most cases there the worst case and the best case is not
going to be separate.
But then in cases such that, such as sorting algorithms, etc., we will see that there are some situations
where the time complexity is going to vary, and in those cases we will have a worst case and a best
case.
Now let's take a look at what Wikipedia has to say about Big-O notation.
So you can see over here it says Big-O notation describes the limiting behavior of a function when the
argument tends towards a particular value or infinity.
So that is what we have seen in the case of asymptotic analysis.
So when n becomes very large or tends towards infinity, we are trying trying to find what the function
becomes asymptotically equal to.
And we are using Big-O notation to express that.
And again it says over.
Here Big-O notation is used to classify algorithms according to how their runtime or space requirements
grow as the input size grows.
So this is what we have talked about time complexity.
And we are going to use big O notation to classify the algorithm accordingly.
All right.
And then over here it also says the letter O is used because the growth rate of a function is also referred
to as the order of the function.
And again big O notation always talks about the upper bound on the growth rate of the function.
So we have got a good understanding about big O and asymptotic analysis.
Now let's take a look at some common complexities in the next point over here.
Now let's say we have identified that the time complexity of an algorithm is O of n.
Now what all does this mean?
Let's try to think of this from multiple angles.
One kind of thought can be that the number of operations is bounded by a multiple of n.
All right.
So it can be 1000 n or a constant into n.
Now you can also think of it in this manner.
As the input size increases the time taken increases linearly.
So this is a linear increase right.
So that would be something like this when you have a graph.
So this is the input size and this is the time taken or the number of operations.
So it's increasing linearly which looks like this.
All right.
Now we can also think of it in this manner.
The number of operations grows proportionally with n.
That means as n increases the number of operations grows proportionally.
So these are different ways of thinking about a time complexity of order of n.
Now, what are some other common complexities we can have?
O of one o of log n o of n o of n log n o of n square o of two to the power n o of n factorial, etc.
and then we can have combinations among them also.
Now let's quickly try to understand what these is.
And then we will keep seeing this in future videos where we write algorithms.
And then we will be analyzing the time and space complexity of each and every algorithm.
And again, remember the same big O notation is also used for space complexity.
But over here let's just discuss time complexity because we have not yet reached space complexity in
this section.
All right.
So we continue with time complexity.
Now if we see that the time complexity of an algorithm is O of one, it means that the time complexity
is constant.
Or as the input size increases, the time required or the number of operations to be done does not increase.
So this indicates constant time complexity.
And in the case of space complexity, it will indicate constant space complexity.
Now O of log n.
Now over here this is another thing O of log n.
And again we have not yet discussed log n.
We will see that soon in this section itself.
So again this is another indication of a time complexity.
For example if we have log n over here.
So let's just navigate between these two.
So over here on the x axis you have n which is the input size.
And on the y axis you have the number of operations to be done.
So you can see that O of one is over here.
That's constant.
So it does not increase.
So the number of operations does not increase as the input size increases.
And then you can see that O of log n is also very good.
Right.
So as n increases the number of operations increases very slowly.
So you have O of log n over here.
Now.
After that you also have o of n.
Now, for example, an example.
Again, I have listed down some examples over here, but don't worry about it.
We will see all of this in the future part of this course.
Now an example where the time complexity is O of log n is the binary search algorithm.
Again, don't worry about it.
Now we will see that in a future video.
Now another common time complexity is O of n.
Now an example is if we have an array and you want to traverse all the elements of the array and add
them, that is, for example, your array is one, two, three, four.
So you want to traverse every element.
So initially you come to one and you add that.
So the sum is one.
Then you move forward.
You come to two.
You add these two so you get three.
Then you move forward.
So three plus three gives you six.
Then you move forward.
And six plus four gives you ten.
So this is an example where you traverse the elements of an array and you are adding them up.
So in this case as the input size increases.
So if n becomes 1000 then you would have to do 1000 operations because you have to traverse each of
those elements.
Right.
So that's an example of an algorithm which has time complexity of the order of n.
Now you can see that of the O of n is something like this.
So it's linear in nature.
All right.
And another common time complexity is O of n log n.
Now an example for this is the merge sort algorithm.
So this is another sorting algorithm where if the elements are given to you something like four then
you have one, two and three.
So using the merge sort you can get these elements sorted.
You can get 123, four.
Again don't worry about this over here.
We will discuss this in a future video.
But the time complexity of this algorithm is O of n log n.
And you can see that this looks something like this.
So o of n log n is worse than o of n and o of log n.
But it's still better than some of these over here.
Now another common time complexity can be O of n square.
Now let's say you are given an array and you want to form all the possible pairs.
That is one and one, one and two, one and three, two and one, two and two, two and three, three
and one, three and two, three and three.
So these are all the possible pairs from these elements.
Right now this type of an algorithm is going to be having a time complexity of order n square.
Again you can see on this chart you have the elements over here and the number of operations.
Now as the input size increases, you can see that the number of operations to be done is increasing
rapidly.
So this is not a good time complexity.
Now another common time complexity can be O of two to the power n.
Now we will see this time complexity in the Fibonacci question.
Again.
Don't worry about it.
We will see that later in the course.
But again just notice the trend over here O of two to the power n.
You can see it's increasing even steeper than O of n square.
And then you have O of n factorial.
Over here you can see as n is increasing it's increasing at a very high rate, right.
It's even worse than O of two to the power n, because in the case of two to the power n, it's just
two into two into two into two, etc..
Right.
But n factorial, let's say let's take an example to understand n factorial.
If you want to find out five factorial, that's actually five into four into three into two into one.
So this is five factorial ten factorial would be ten into nine into eight into seven, etc. up to one.
So you can see that in these cases most of the terms are greater than two.
And over here every term is two itself.
So that's why n factorial is going to be greater than two to the power n.
So you can see that it is having a very steep rise.
So as the input size increases, the number of operations to be done is increasing in a very steep manner.
So these are some common time complexities.
And then the interesting thing of this graph is that it clearly depicts the trend.
And Big-O analysis is all about the trend.
So we are interested about the trend.
So if you have an algorithm that has a time complexity of O of N, and then you have another implementation
for the same question, and that algorithm has a time complexity of O of n square.
Then you should be able to understand that this implementation is much better, because as the input
size is increasing, the number of operations to be done is increasing at a much lower pace than the
implementation, where the time complexity is O of n square.
So by finding the time complexity of an algorithm, we can compare that algorithm with another algorithm.
Maybe both of them are solving the same question and we can identify which algorithm is better.
So we have taken a look at some common complexities.
Now let's go ahead and take a look at space complexity.