✏️ Explanatory Question
The efficiency of doIt() is
5n. A loop runs n times and calls
doIt() during each iteration. Calculate the overall
efficiency.
for (i = 1; i <= n; i++) {
doIt();
}
The efficiency of doIt() is
5n. A loop runs n times and calls
doIt() during each iteration. Calculate the overall
efficiency.
for (i = 1; i <= n; i++) {
doIt();
}
Ans. The loop calls doIt()
n times, and each call costs 5n.
Total efficiency = n × 5n = 5n2
Therefore, the run-time efficiency is O(n2).
💡 Explanation:
The outer loop executes n times. During every
iteration, it calls doIt(), whose efficiency is
5n.
Since the method cost occurs during every loop iteration, multiply the loop count by the cost of one method call:
n × 5n = 5n2
In Big-O notation, the constant coefficient 5 is removed because it does not affect the growth rate. Hence:
O(5n2) = O(n2)
Memory tip: When a loop calls a method whose cost depends on n, multiply the loop's complexity by the method's complexity.