What is the tight asymptotic time complexity of the following code? sum = 0;…
2020
What is the tight asymptotic time complexity of the following code?
sum = 0;
for (i = 1; i <= n; i *= 2)
for (j = 1; j <= n; j++)
sum++;Answer: B. O(n log n) — ConceptFor nested loops, the total operation count is obtained by multiplying the iteration count of the outer loop by the work performed during each outer…
- A.
O(n2)
- B.
O(n log n)
- C.
O(n)
- D.
O(n log n log n)
Attempted by 593 students.
Show answer & explanation
Correct answer: B
Concept
For nested loops, the total operation count is obtained by multiplying the iteration count of the outer loop by the work performed during each outer iteration. A loop whose control variable doubles follows a geometric sequence and executes Θ(log n) times.
Application
The outer-loop values are i = 1, 2, 4, …, 2k. The loop continues while 2k ≤ n, so it executes ⌊log2 n⌋ + 1 times.
For each outer iteration, the inner loop takes j through 1, 2, …, n and increments sum exactly n times.
Therefore, the total number of increments is n(⌊log2 n⌋ + 1), which is Θ(n log n).
Cross-check
When n doubles, the inner-loop work doubles and the outer loop gains only one additional iteration. This growth pattern agrees with Θ(n log n), so the matching asymptotic option is O(n log n).