What is the time complexity of the function fun() below? int fun(int n) { int…
2024
What is the time complexity of the function fun() below?
int fun(int n)
{
int count = 0;
for (int i = n; i > 0; i /= 2)
for (int j = 0; j < i; j++)
count += 1;
return count;
}Answer: C. O(n) — Concept: When an inner loop's iteration bound depends on the outer loop's current value, the total operation count is the sum of the inner-loop iterations…
- A.
O(n2)
- B.
O(n log n)
- C.
O(n)
- D.
O(n log(n log n))
Attempted by 239 students.
Show answer & explanation
Correct answer: C
Concept: When an inner loop's iteration bound depends on the outer loop's current value, the total operation count is the sum of the inner-loop iterations over every outer pass — not simply the outer-pass count times the inner-pass count. If the outer variable shrinks geometrically (halves each pass), this sum forms a geometric series, which converges to a small constant multiple of its largest term.
Application:
The outer loop runs with i = n, n/2, n/4, ..., continuing while i > 0, so it makes roughly log₂ n + 1 passes.
For each value of i, the inner loop runs exactly i times (j goes from 0 up to i − 1), adding i to count.
So the total operations = n + n/2 + n/4 + ... + 1, a geometric series whose first term is n and common ratio is 1/2.
This infinite geometric-series formula gives an upper bound of 2n; the actual finite sum (stopping once i reaches 0) is slightly less than 2n, as the cross-check below confirms.
Big-O drops the constant factor, so the time complexity is O(n).
Cross-check: For n = 16, the inner-loop counts are 16, 8, 4, 2, 1, which sum to 31 — just under 2 × 16 = 32, confirming the series converges to about 2n. That linear total rules out n² (256) and n log n (64) for the same input.