Calculate the run-time efficiency of the following program segment (three nested loops):
i = 1
loop (i <= n)
j = 1
loop (j <= n)
k = 1
loop (k <= n)
print(i, j, k)
k = k + 1
end loop
j = j + 1
end loop
i = i + 1
end loop
Answer:
There are three nested loops, and each loop executes
n times. Therefore:
Total iterations = n × n × n = n3
Hence, the run-time efficiency is O(n3).
💡 Explanation:
The outer loop executes n times. For every
iteration of the outer loop, the middle loop also executes
n times. Similarly, for every combination of
i and j, the innermost loop executes
n times.
Therefore, the print(i, j, k) statement executes
once for every possible combination of
i, j, and k.
Number of combinations = n × n × n = n3
General Pattern:
If there are k independent nested loops and each
loop executes n times, the resulting time
complexity is O(nk). Here,
k = 3, so the complexity is
O(n3).