Analyzing control statements

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.

Example - 1

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:

1. var sum = 0; - takes $$O(1)O(1)$$ time

2. var i = 0; - takes $$O(1)O(1)$$ time

3. i<n; - takes $$O(1)O(1)$$ time

4. i++; - takes $$O(1)O(1)$$ time

5. sum = sum + ar[i]; - takes $$O(1)O(1)$$ time

6. 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:

Running time of the above algorithm

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)$$.

Example - 2

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)$$.

Example - 3

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)$$.

Conclusion

We have seen that what are the control statements and how to analyse them using multiple examples.
Thanks for the reading the article.