Analyzing Control Structures in Algorithm

Analyzing control structures is essential from the perspective of understanding the running time of an algorithm. Sequential structures, looping structures, control structures, recursive calls, and so on are all part of programming languages. We shall examine the complexities of each of them here.

The following is the relationship between the order of growth rate:

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < n! < nⁿ

Sequential execution

Statements or blocks of statements appear one after the other in sequential structures. Assume B1 and B2 are two blocks of instructions, each of which might contain a single instruction, several sequential instructions, or a collection of complicated instructions.

The execution of B1 and B2 are indicated in the figure to be consecutive. Assume that the time taken by code of B1 is t₁ and the time taken by code of B2 is t₂.

If B1 and B2 are executed in sequential order than the complexity of the entire program will be,

T(n) = t₁ + t₂ = max (t₁, t₂)

In a complexity study, the order of code blocks is irrelevant. In general, if the program has m modules (or m functions), then the total complexity of the program is determined by first determining the complexity of each module, i.e. t₁, t₂,…, t_m. Find the maximum time for all of them; this is the overall program’s complexity.

T(n) = max (t₁, t₂, t₃, …, t_m)

T(n) = max (t₁, t₂, t₃,…,t_m) = max (t₁, t₂, t₃, t₄)

= max (O(n³), O(n), O(n⁴), O(n²))

= O(n⁴) 

If else

The execution of B1 and B2 is now conditional on a number of factors. If the condition is met, the B1 block is executed; if the condition is not met, the B2 block is executed.

T(n) = max (t₁, t₂)

T(n) = max (O(n), O(n²)) = O(n²)

For loop

For loop executes inner statements n times if loop is set to iterate n times. Following code blocks explain the running time of for loop

for (i = 1; i ≤ n; i++)
{
  Count = Count + 1;
}

Cost of the inner statement is O(1) and for loop iterates n times.

for (i = 1; i ≤ n; i++)
{
  for(j = 1; j ≤ n; j++)
  {
    Count = Count + 1;
  }
}

While loop

Running time of while loop and for loop is computed in similar way. Complexity of code block is given by total cost of inner most statement in loop. Let’s analyze few code segments containing while loop:

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

Inner statement executes n times, so T(n) = O(n)

i = 1;
while(i  ≤  n)
{
  j = 1;
  while(j  ≤  n)
  {
    Count = Count + 1;
    j = j + 1;
  }
  i = i + 1;
}

Inner most statements executes n times for each value of i, and loop of I itself iterates n times. So,

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

Here, decrement of n is not in linear order. Value of n is reduced by factor 2, maximum log₂n divisions are possible before n reduce to 0. So,

T(n) = O(log₂n)

while(n > 0)
{
  n = n / m;
}

In the above code, n reduces by factor m in every iteration, so while loop can iterate maximum log_mn times.

T(n) = O(log_m n)

---

Additional Reading: Analyzing Control Structures [PDF]