ExamCompetition Your Success, Our Mission
Login Register
Question discussion

What is the time complexity of the following code fragment?for (i = 1; i < n; i *= 2) for (j = 0; j < i; j++) count++;

1111Medium DSSSB TGT Computer Science 0 replies 1 views
0

What is the time complexity of the following code fragment?

for (i = 1; i < n; i *= 2)
    for (j = 0; j < i; j++)
        count++;
  • AΘ(n log n)
  • BΘ(log n)
  • CΘ(n)
  • DΘ(n²)
Correct answer: C

Explanation

The inner loop runs 1, 2, 4, …, n/2 times, a geometric series that sums to about n, so the total work is Θ(n).
Join the discussion Report an error

Discussion 0

Nobody has replied yet. Start the discussion!