What is the complexity of the following code ? sum = 0; for (i = 1; i <= n;…

2020

What is the complexity of the following code ? 

sum = 0;
  for (i = 1; i <= n; i*= 2)
    for(j = 1; j <= n; j++)
      sum++;

Which of the following is not a valid string ?

  1. A.

    Ο(n2)

  2. B.

    Ο(n log n)

  3. C.

    Ο(n)

  4. D.

    Ο(n log n log n)

Attempted by 188 students.

Show answer & explanation

Correct answer: B

The outer loop iterates logarithmically (log n) as i doubles each time. The inner loop iterates linearly (n). Multiplying these gives a total time complexity of O(n log n).

Explore the full course: Isro