The efficiency of doIt() is
O(n2). A loop doubles the value of
i after every iteration and calls doIt().
Calculate the overall efficiency.
for (i = 1; i <= n; i = i * 2) {
doIt();
}
Ans. The loop executes approximately
log2(n) times, and each call to
doIt() costs n2.
Total efficiency = log2(n) × n2 = O(n2·log2 n)
💡 Explanation:
The values of i are
1, 2, 4, 8, 16, …. Because i doubles
after every iteration, the loop reaches n after
approximately log2(n) iterations.
During every iteration, doIt() is called once, and each
call requires n2 operations.
Therefore:
log2(n) × n2 = O(n2·log n)
Memory tip: A loop that repeatedly doubles or halves its variable has O(log n) iterations. Multiply this by the complexity of the operation performed inside the loop.