Hello Everyone, I hope you are all safe and in good health.
This is Madhav Gupta and today I'm here to throw some light over finding time complexities of algorithms. This can also be taken as a prerequisite for my upcoming DSA(data structures and algorithms) articles which I'll be writing in the coming future.
All of us face the questions of complexity in our interviews and we should know in general how to find complexities because it makes us a better engineer.
Now let's focus because
So coming on to the point, there are some rules which you should keep in mind while finding complexity of the given algorithms and these are -
- Ignore constants.
- Take the biggest degree in the expression formed.
- Break your code into segments and analyse them one by one.
Also, there's one thing which we need to keep in mind, n is significantly large in our case for which we find time complexity.
Let's talk about statements which take linear time.
- Declarations and operations - These are the statements which always take linear time and examples of some of them are
int x=0
x=x+1
x=x-1
x=x*4
All of the above statements if executed independently would run in O(1) time.
After talking about the statements that execute in linear time, let's talk about loops. I can already find it getting exciting and more challenging as we progress through the article.
- Loops - Now things start changing from here, because iterations gets repeated and time complexity here is equal to number of times the loop ran. Let's look at the following code - ```
for(int i=0;i<n;i++){
a=a+2;
}
So, if we try to find how many times the statement *a=a+2* executed, we would get that *a=a+2* executed n number of times.
Suppose if statement *a=a+2* is taking k seconds to execute(k is constant), then our time function here would be
T(n) = kn.
That would give us time complexity as **O(n)**.
Let's take various instances in loops and let's analyse them one by one.
---
for(int i=n;i>0;i--){
print("*");
}
In the above case, now i is n in the starting and it is decreasing by one. The loop stops but when i becomes 0.
The main thing to analyse here is that even if our i is decreasing, the number of iterations remain the same. Hence this loop is also having the time complexity of **O(n)**.
---
for(int i=1;i<=n;i=i+2){
print("*");
}
In the above case,i is increasing at the rate of 2. That means the time function here would look something like this
T(n)=n/2
As we know we have to take only the biggest degree in our expression. Hence the above for loop would take time complexity as **O(n)**.
Even if i is increasing at a rate of 20, the time complexity of would remain the same.
___
for(int i=1;i<n;i=i*2){
print("*");
}
Now here the case is different. Here i is multiplying itself with 2. Let's look at the value of i with every iteration.
|Iteration|i|
|:----|:----|
|1|1|
|2|2|
|3|4|
|.|.|
Let's suppose the loop ends at the k-ith iteration, so the value of i at k-ith iteration would be 2<sup>k</sup>.
2<sup>k</sup>=n
Taking log both sides,
k=log<sub>2</sub>n
Hence the time complexity in this case would be **O(log<sub>2</sub>n)**. The same would be the case when i starts with n(loop ends at 1) and it keeps itself dividing by 2.
___
for(int i=0;i*i<n;i++){
print("*");
}
Here the case is that when i*i i.e. i<sup>2</sup> would become equal to n, then the loop would stop.
So let's assume the loop stops at i=k.
So, k*k = n
k<sup>2</sup> = n
k = <span>√n</span>
Hence the time complexity in this case would be <b>O(<span>√n</span>)</b>
I know it might feel boring at first but it's really necessary to understand how it all works under the hood. Otherwise, all of us can memorise that the time complexity of selection sort is O(n<sup>2</sup>). But we should also understand how it came there in the first place.
Now comes the most important instance in for loops.
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
print("*");
}
}
Let's analyse the above loop first, how many times the statement `print("*")` would execute. For i=1 the inner loop would execute n times, for i = 2 the inner loop would execute n times again and for i = n, the inner loop would execute n times.
Hence the total number of times the statement `print("*")` got executed = n+n+n+..n times
T(n) = n(1+1+1+..n times)
T(n) = n * n
T(n) = n<sup>2</sup>
Hence the time complexity for nested for loops is **O(n<sup>2</sup>)**
___
While we were at it, we have completed our loops part already. I congratulate you for making it this far. Give yourselves a pat on your back and let's talk about if-else block.
___
* If-else statement - We take the time complexity of the block for whichever it is larger. The following example would clear it out.
// Time complexity = O(1)
if(i==0){
print("");
}
// Time complexity = O(n)
else{
for(int i=0;i<n;i++){
print("");
}
}
As we can see in the above code that if block is having O(1) and else block is having O(n). Hence the time complexity of the whole if-else block would be **O(n)**(since O(n)>O(1)).
___
* Consecutive Statements - We add the time complexities of each statement. Here's is an example
// takes O(1) time
int m=0;
// takes O(n) time
for(int j=1;j<=n;j++){
print("*");
}
// takes O(n^2) time
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
print("*");
}
}
Taking into consideration the constant time of each print statement too.
Total cost = c<sub>0</sub>+c<sub>1</sub>n+c<sub>2</sub>n<sup>2</sup>
Taking the biggest degree,
Hence time complexity = **O(n<sup>2</sup>)**
___
Phewww, That was really a long article, wasn't it?
With that being said, it really feels good to be writing again. In this article i explained all the basics we need to find time complexities for common algorithms. I'd be bringing part 2 of the same topic with lots of questions which we would practice together and it would further strengthen our understanding.
I would attach the link of part 2 whenever i post the next part so be sure to save this one.
Please let me know if you liked this one or not, I'd gladly accept any criticism that comes my way and return with better content.
Top comments (0)