What is the tight asymptotic time complexity of the following code? sum = 0;…

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

1. The outer-loop values are i = 1, 2, 4, …, 2k. The loop continues while 2k ≤ n, so it executes ⌊log2 n⌋ + 1 times.

2. For each outer iteration, the inner loop takes j through 1, 2, …, n and increments sum exactly n times.

3. 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).