If the algorithm doIt() has an efficiency factor of
5n, calculate the run-time efficiency of a program
segment containing a loop that runs n times and calls
doIt() during each iteration.
Answer:
The loop calls doIt() exactly n times,
and each call requires 5n operations.
Total work = 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 run-time cost is
5n. Therefore, the loop count and the function
cost must be multiplied:
n × 5n = 5n2
In Big-O notation, constant coefficients are ignored. After removing the constant 5, the final complexity is O(n2).
Key Idea:
When a loop calls a routine whose own cost depends on
n, multiply the number of loop iterations by the
cost of that routine.