How do we count number of operations when we have nested loops?

When analyzing algorithms, the product rule is frequently used to determine the number of operations. It could be applied to nested operations.

Product rule

The product rule in counting states that if there are $n_1$​ ways to perform the first task, $n_2$​ ways for the second task and $n_k$​ ways for the $k-$th task, then the total number of ways to perform all tasks is $n_1 \times n_2 \times \ldots \times n_k$​. It is used to calculate the total outcomes when events are independent. The formula is expressed as the product of the individual possibilities for each task.

Applying product rule on nested loops

Counting the number of operations in nested loops involves determining how often the innermost statement or statements are executed. Let’s break down the process:

Consider a set of nested loops like this:

The numbers here indicate how many iterations there are in the outer loop ($n$) and how many there are in the inner loop ($m$). To tally the quantity of procedures:

• The outer loop runs $n$ times.

• The inner loop iterates $m$ times for each outer loop iteration.

• The total number of operations is given by multiplying the number of operations in the outer loop by the number of operations in the inner loop.

  • Total operations = $n \times m$

Example

For example, if we want to count how many number of operations will be there if there are three nested loops.

For the above example the innermost operation will be executed a total of $2 \times 4 \times 7 = 56$ times.

Note: If there are more nested loops, we continue this process, multiplying the number of operations for each additional nested loop.

It’s worth noting that big-O notation is often used to describe the time complexity of algorithms, especially when the input size is large. The number of operations in terms of big-O notation focuses on the dominant term and simplifies the expression to provide an understanding of how the algorithm’s performance scales with input size. For example, if we have the following nested loops, the big-O notation will be:

• The outer loop runs $n$ times.

• The middle loop runs $m$ times.

• The innermost loop runs $m−n$ times.

Now, let’s calculate the total number of iterations:

The dominant term in the expression is $n \times m \times m$, so the time complexity is $O(n \times m^2)$. The constant factor is omitted in big-O notation, so $O(n \times m^2)$is the simplified time complexity for this nested loop structure.