In coding interviews.
Once you've come up with a solution and written an algorithm to solve the question, it's very important
to be able to check whether your algorithm is efficient or not.
For that, you would have to compute the time and space complexity of the algorithm that you have written.
And for this you would make use of Big-O analysis.
All right.
So this is the industry standard.
Now in this video let's develop a strong base for Big-O analysis.
All right.
And for this the best way is to explore this through questions and answers.
So these are the eight things that we will explore in this video.
First we start with trying to understand what is the need for complexity analysis.
Later we will take a look at time complexity as well as space complexity.
So let's start with point number one and develop an intuition and understand what the need is for complexity
analysis.
So let's say you are given a question.
You have to write an algorithm where you will be given the input which is n and the output which is
required is n minus one plus n minus two, etc. up to one.
So for example if n is equal to five, then the output would be four plus three plus two plus one.
All right.
So this over here is equal to ten right.
Four plus three is seven seven plus two is nine and nine plus one is ten.
So the output required if n is 5 in 5 is equal to ten.
All right.
Now let's say this is the question.
Now one solution for this let's say person A writes an algorithm for this.
So the way he approaches it is that he's just going to compute n minus one into n divided by two.
So again if n is equal to five this is for n minus one is four and n is five divided by two.
So this gives ten.
All right.
Now another person writes an algorithm.
Let's say he's writing a loop.
So he's going to iterate from n -1 to 1 and keep adding the values.
So that means first he takes four.
He adds 4 to 3.
So he gets seven.
Then to seven two is added.
So that becomes nine and then to nine.
One is added and he gets the output ten.
So both of these get the answer ten right.
So both these people get the answer ten, which is correct.
It's not that the answer is wrong, but then which approach is better.
Let's think of these three questions.
Which approach among these two is better and even why care about identifying which is better?
Is that even needed?
And then what does better mean?
So let's take a look at these three questions.
First, let's take a look at the second question.
Why should we care about identifying which approach is better now, especially in real life applications
where we talk about algorithms, where there can be huge amount of data, there can be significant performance
differences between solutions.
All right.
So that is why it's very important to identify the better solution for problems that we encounter.
Now when we talk about huge amount of data, it can be in terms of millions or billions of data points.
Now it should be very much familiar to you.
You can just think of things like Facebook or Twitter etc., which have billions of users.
Right?
So and again, there are various applications where a huge amount of data is involved.
So that is why it's always important to identify the best solution to problems that we encounter.
So that's this question over here.
Now when we say that we need to identify which among these two solutions is better, what does actually
better mean now in terms of computers and algorithms, better means faster and solutions that consume
less memory.
So these are going to be the two criterias, on the basis of which we will evaluate the algorithms that
we will write.
All right.
Now we come to the third question which is which approach among these two is better.
Now how do we identify that for this?
Again over here we have already identified that better means faster and less memory.
Now to identify which among these is faster, we will make use of the concept of time complexity and
to identify which consumes less memory.
We have the concept of space complexity.
All right.
So we have done with we are done with question one.
We have understood why there is a need for complexity analysis especially.
This is important because we deal with huge amount of data.
Now let's look at the second question over here.
What is time complexity?
We have seen that we make use of time complexity to identify which algorithm is faster.
Now over here again we have the same example.
We have the question where the input is n and the expected output is n minus one plus n minus two,
etc. up to one.
And we have these two approaches of solving this question.
Now let's try to understand what is time complexity in this perspective.
With this example.
And again we are using time complexity to identify which approach is faster.
Now when we talk about an algorithm being faster, we are not going to measure whether this algorithm
takes one second and this takes two seconds, etc..
Right.
It's not going to be in terms of seconds or the amount of time that an algorithm takes to run.
Now why is that?
So let's try to understand why this is the case.
It's because if we run the same algorithm on the same machine in two instances, we are going to get
different time.
So that's one reason.
And the second reason is that if we have different machines which have different hardware, then the
same algorithm is going to take different time on those two machines.
All right.
So again you can notice this if you use some plugin to measure the time which an algorithm takes when
it runs.
If you run the same algorithm two times, you will see that it will take different amount of time to
run the algorithm.
That's because multiple things are happening on the computer at the same time, right?
So the same algorithm run on the same machine at two instances is going to take different amount of
time.
And secondly, this is intuitive.
If you have different machines and they have different hardware capabilities, the same algorithm is
going to take different amount of time in terms of seconds on both the machines.
So that's why we are not going to measure the time complexity or the amount of time or which algorithm
is faster in terms of the seconds that an algorithm takes.
All right.
So this is not going to be way going to be the way that we compute the time complexity.
Now if that is not the case then how do we proceed.
The way by which we are going to compute the time complexity is rather, by counting the number of simple
operations the computer has to do to execute the algorithm.
So we are going to count the number of simple operations.
Now a simple operation is going to take constant time.
All right.
So or it's going to take the least amount of unit time.
So that's why by counting the number of operations this is not going to vary from time to time.
Right.
So if you run the same algorithm two times on the same machine, the number of operations the algorithm
or the computer has to do to execute the algorithm is not going to change.
And even if you have two machines with different hardware capabilities, and if you're executing the
same algorithm on both the machines, the number of simple operations the computer has to do to execute
the algorithm is going to be constant.
So that is why we are going to compute the time complexity.
By counting the number of simple operations the computer has to do.
All right.
So this is how we are going to do it.
Now let's try to look at these two solutions.
So over here how many simple operations are there.
So we have to do a division a subtraction and a multiplication.
Right.
So we can say that we have to do at least three simple operations to find the value over here.
And what about the second solution?
Let's say the let's take an example.
Let's say n is equal to five.
So if n is equal to five we have to do four plus three plus two plus one.
So to find this these numbers right 432 and one.
So we have to find four numbers.
So that's because n is equal to five.
So identifying these four numbers is n minus one operations.
And then we have to do n minus two operations to add them.
Right.
So we are doing one addition over here when addition over here one addition over here.
So that's at least n minus two operations.
So if we add n minus one and n minus two we get two n minus three.
So over here we have seen that we have to do three operations.
But over here we have to do two n minus three operations.
So now we are where are we at.
Just let's let's track where we are.
We identified that we wanted to check the time complexity to see how fast an algorithm performs.
And we have established that to do this we are going to count the number of simple operations the computer
has to do.
Now we have applied this in the case of the example which we are dealing with.
So over here there are three operations.
And over here there are two N minus three operations.
Now we are actually not interested in the exact number.
Like for example it's three over here and it's four plus three which is seven over here.
If n is equal to five we are not exactly interested with the exact number.
The idea over here is that what happens when the number when the input scales.
Right.
So if n is equal to 1000 also over here it's going to be three.
But over here it's going to be around 2000 right.
It's going to be 2000 minus three.
So you can see that this algorithm is going to be more efficient.
Because if you have n as 1 million also we are just going to two three operations.
So we can establish that the time complexity is better for this algorithm rather than for this algorithm.
Now again, a quick side note over here.
The way that we wrote the two algorithms for this question over here is by using a formula in one case.
All right.
So this is just a formula.
Now this is not always the case.
Typically in coding interview questions you would have to decide which data structure to use because
different data structures have different time and space complexity when it comes to doing different
operations.
So typically you will have to make this choice.
So that's why it's important to have a good understanding about the various data structures.
And then even you will have to decide whether the solution which you are implementing is going to be
iterative or recursive, etc..
So again, don't worry about this.
We will see this in upcoming videos.
Again, recursion means a function which calls the same function again and again until the solution
is reached, right?
So that's recursion.
And iteration is like having a for loop.
But again don't worry about this.
Again I'm just mentioning this.
This over here is that whenever we decide what approach to take to solve a question, what is the parameter
that we should be thinking about?
It's going to be what the implication of our decision is with respect to the time complexity, as well
as the space complexity.
All right.
So let's get back to this example.
Over here.
We have seen that we have counted the number of simple operations.
And in this case we only have to do three operations.
But over here we have two and minus three operations.
And hence this solution over here is more efficient than this one because as n scales or as n becomes
very huge, this is still just going to be three.
But this is going to become huge, right?
So we are interested when we talk about time complexity in the fact in, in trying to understand as
n or as the input grows, in what proportion does the number of operations that the computer has to
do grow?
So this is going to be what time complexity is.
So with time complexity we are actually checking whether the algorithm is.
Good and whether it would scale.
Right.
So whether will it work efficiently when n becomes very large.
So that is why time complexity is extremely important.
So in other words, we can say that time complexity is nothing but how the runtime grows as the input
size grows.
So again runtime is measured in terms of the number of operations, not in terms of seconds.
So time complexity can be defined as how the runtime of an algorithm grows as the input size grows.
All right.
So this is time complexity.
And to identify this we again let me just write this over here.
How runtime grows as the input size grows.
This is what we call time complexity.
And to find the time complexity, that is, to find what in what proportion the number of operations
will grow as the input grows.
We are going to do something called asymptotic analysis.
All right.
So this is just a fancy word.
So this deals with what in what proportion does the number of operations grow as the input grows.
So this is what we call asymptotic analysis.
So we will see that in the next question.
So this is point number two.
In point number three we will analyze this in greater depth.
All right.
And the asymptotic analysis is going to be expressed using Big-O notations.
So that is big over here.
All right.
So we have got an introduction to asymptotic analysis and Big-O notations.
All right.
So let's go ahead and dive deeper into this in the next point.
And one more point before we close this part over here.
When we say that, in what proportion does the number of operations grow as the input size or as n grows?
We are only interested in the general trend.
We are not interested in precision, right?
We don't want to know whether the number of operations is five or 10 or 12.
Right.
We want to know the trend, right?
For example, if we have a graph and let's say this is the input size and this is the number of operations
on the y axis, we want to know if n is increasing.
Does the number of operations grow in this manner.
Is this the trend or is the trend something like this?
Is it growing going to grow exponentially?
So we are interested in the trend not in precision.
All right.
Now let's go ahead.
So we have covered these two points.
We have understood the need for complexity analysis.
And we have understood what time complexity is which is nothing.
But how does the runtime increase when the input size increases.
And we have seen that to identify this, to identify the time complexity, we have to do something called
asymptotic analysis.
And the asymptotic analysis is expressed using Big-O notations.
So let's go ahead and look at three and four next.
So first we start with asymptotic analysis.