Analyzing Algorithm Control Structure in DAA

To study the overall performance of a programming code or algorithm, each instruction must be examined independently. However, some algorithm control structures are included in every programming code and have their own asymptotic analysis. Control Structures are just a method of describing the flow of control in a program. If self-contained modules, known as control structures, are used, any algorithm or program may be made more simple and understandable. This article gives you details of analyzing different control structure in an algorithm or program.

Sequencing

Suppose an algorithm has two blocks, Block A and Block B, which takes time T_A and T_B respectively, for computation. According to the sequence rule, the total computation is (T_A + T_B) and thus, computation time is (max (T_A,T_B)) according to maximum rule.

For example, Let us suppose T_A =O (n) and T_B = θ (n²).

Then, Computation Time = T_A + T_B = (max (T_A,T_B) = (max (O (n), θ (n²)) = θ (n²)

Sequencing

If-Then-Else

If-Else

In If-then-else, algorithm have to select only one block according to given condition. An algorithm have two blocks, Block A and Block B, which takes time T_A and TB, respectively, for computation; however, according to if-elsecondition, only one block, either Block A or Block B, will be executed. So, the total computation time will be Max(T_A,T_B), according to maximum rule.

For example, suppose T_A =O (n²) and T_B = θ (n²).

Total Computation = (max (t_A,t_B)) = max (O (n²), θ (n²))= θ (n²)

For Loop

For loop is used when we want to repeat a group of statements over and over again. This loop guarantees that the collection of statements we wish to repeat is performed as many times as we wish. Let us analyze it with the help of an example:

For Loop Analysis

The Assignment and arithmetic operations are considered as constants while calculating complexity, therefore, their time complexities are represented as O(1). Secondly, in loop “i<n”, the variable “i” is dependent on the input variable “n”. So, the larger the input size n, the longer the program will run, hence it is not constant, i.e., O(n).

Time complexity Big “O”=O(1) + O(n)= O( 1 + n)

Nested Loops

Nested loop refers to loop inside another loop. Let’s see its analysis with the help of example.

Nested Loop Analysis

In this example we have  two loops, both the inner loop  and the outer loop are dependent on the input size ‘n’. So, we have two O(n) and two constant O(1).

The time complexity, Big “O”= ( O(1) + O(n) + O(n) ) = O ( 1+ n + n)

Ignoring the constant O(1), we get Big “O”= O ( n²)

While Loop

The simplest method for analyzing the loop is to figure out the purpose of the variable involved, whose value lowers with each iteration. That value must be a positive integer in order for the loop to be terminated. The number of repetitions of the loop may be calculated by keeping track of how many times the value of the function lowers. Let us see in following examples:

Example 1:

while ( n > 0 ) {
…
n = n – 1
}

The time for the above code will be Θ(n)

Example 2:

while ( n > 0 ) {
…
n = n / 2
}
i = 0; j = n

In this example code, total computation will be equal to Θ(log n)

Example 3:

while ( i < j ) {
…
i++; j–;
}
In this case, the computation time taken by the code will be Θ(n)