Engineer bro!
Sun May 01 2022 (11 months ago)
Engineer by mistake!
I am a software engineer by passion
Controls statements are basic building blocks for any algorithm, they decides that how your program will behave. Algorithm's control flow entirety depends on the control statements present in the algorithm. So, it's important to learn that how can we analyse the controls statements of an Algorithm.
Consider an algorithm for getting sum of all number present in the array. You will be given an array of numbers as input.
# Input : Integer A[n] array of integers, N length of the array
# Output : Sum of all numbers in the array
// Algorithm
function Sum(ar,n){
var sum = 0; // initial sum
for(var i=0; i<n; i++){
sum = sum + ar[i];
}
return sum;
}
Let's notedown all the controls statement of the above algorithm:
var sum = 0;
- takes $$O(1)O(1)$$ time
var i = 0;
- takes $$O(1)O(1)$$ time
i<n;
- takes $$O(1)O(1)$$ time
i++;
- takes $$O(1)O(1)$$ time
sum = sum + ar[i];
- takes $$O(1)O(1)$$ time
return sum;
- takes $$O(1)O(1)$$ time
As you can see the for loop in the above algorithm will run for n
times, so statement 2,3,4,5 will also run for n
times.
We can write the total time taken by the algorithm as follows:
The time complexity of the above algorithm is $$f(n)=4n+2f(n)=4n+2$$. The estimated running time for various values of n is as follows:
n | Steps |
---|---|
1 | 6 |
5 | 22 |
100 | 402 |
1000 | 4002 |
10000 | 10002 |
You can see that as n grows, the number of steps grows in linear proportion to n for the given algorithm sum. The dominating term of the function in time completely is n. As n gets large +2 terms becomes insignificant.
So, we write the time complexity of the above algorithm as $$T(n)=O(n)T(n)\; =\; O(n)$$.
sum = a + b;
The above statement in the algorithm will be executed only once. So, time complexity would be $$T(n)=O(1)T(n)\; =\; O(1)$$.
for(var i=1; i<n; i++){ // loop1
for(var j=1; j<n; j++){ // loop2
sum = a + b;
}
}
The loop1 will execute for n
times and it has some constant operations like initialising i, updating it, etc. loop2 will also execute for the same amount of time along with some constant operations.
According to the above image we can have the time complexity calculation as follows:
So total time complexity could be calculated as follows:
We can ignore the lower order term and keep only the higher order term. So, we could write $$T(n)=O({n}^{2})T(n)\; =\; O(n^2)$$.
We have seen that what are the control statements and how to analyse them using multiple examples.
Thanks for the reading the article.
© 2021 dsabyte. All rights reserved