✏️ Explanatory Question
Q. If the efficiency of doIt() is
O(n²), calculate the efficiency of the following
logarithmic loop:
for (i = 1; i <= n; i = i * 2) {
doIt();
}
Q. If the efficiency of doIt() is
O(n²), calculate the efficiency of the following
logarithmic loop:
for (i = 1; i <= n; i = i * 2) {
doIt();
}
Ans. Since i doubles after every iteration,
the loop executes approximately log₂(n) times.
Total efficiency = log₂(n) × n² = O(n² log₂ n).
💡 Explanation:
The values of i progress as
1, 2, 4, 8, 16, … until they exceed
n. Because the value doubles each time, the loop
reaches n after approximately
log₂(n) iterations.
During every iteration, doIt() is called once, and each
call requires n² operations.
Therefore: log₂(n) × n² = O(n² log n).
Memory tip: A loop that repeatedly doubles or halves its variable usually has logarithmic complexity, O(log n).