Calculate the run-time efficiency of the following three nested loops, where each loop runs n times:
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
for (k = 1; k <= n; k++) {
print(i, j, k);
}
}
}Ans. Each of the three nested loops runs n times. Therefore:
n × n × n = n3
Hence, the run-time efficiency is O(n3).
💡 Explanation:
The outer loop runs n times. For every outer-loop iteration, the middle loop also runs n times. Similarly, for every combination of the outer and middle loops, the inner loop executes n times.
Because the loops are nested, their iteration counts are multiplied:
Total iterations = n × n × n = n3
The print(i, j, k) statement performs constant work during
each iteration. Therefore, it executes n3
times, giving a final time complexity of
O(n3).
Memory tip: If k nested loops each run n times, their time complexity is generally O(nk). Here, k = 3, so the result is O(n3).