✏️ Explanatory Question
If the efficiency of doIt() is O(n²), calculate the efficiency of the following segment:
for (i = 1; i <= n; i++) {
for (j = 1; j <= n - 1; j++) {
doIt();
}
} If the efficiency of doIt() is O(n²), calculate the efficiency of the following segment:
for (i = 1; i <= n; i++) {
for (j = 1; j <= n - 1; j++) {
doIt();
}
}Ans. The outer loop runs n times, while the inner loop runs n − 1 times for each outer-loop iteration.
Total efficiency = n × (n − 1) × n² = n⁴ − n³ = O(n⁴).
💡 Explanation:
The two nested loops execute the statement
n × (n − 1) times. During every iteration,
doIt() is called, and each call requires
n² operations.
Therefore: n × (n − 1) × n² = n⁴ − n³.
In Big-O notation, only the highest-growing term is retained. Since n⁴ grows faster than n³, the final time complexity is O(n⁴).