The efficiency of doIt() is
O(n2). An outer loop runs
n times, and an inner loop runs
n − 1 times while calling doIt().
Calculate the overall efficiency.
for (i = 1; i <= n; i++) {
for (j = 1; j <= n - 1; j++) {
doIt();
}
}
Ans. The outer loop runs n times, the
inner loop runs n − 1 times, and each call to
doIt() costs n2.
Total efficiency = n × (n − 1) × n2 = n4 − n3
Therefore, the overall efficiency is O(n4).
💡 Explanation:
The two nested loops produce
n × (n − 1) total iterations. During every
iteration, doIt() is called once, and each call requires
n2 operations.
Multiply the loop counts by the cost of one call:
n × (n − 1) × n2 = (n2 − n) × n2 = n4 − n3
In Big-O notation, only the fastest-growing term is retained. Since n4 grows faster than n3, the final time complexity is O(n4).
Memory tip: Multiply the complexities of nested loops and the operation performed inside them, and then keep only the dominant term.