Let A[1, ..., n] be an array storing a bit (1 or 0) at each location, and f(m)…

PYQ GATE 2004

Let A[1, ..., n] be an array storing a bit (1 or 0) at each location, and f(m) is a function whose time complexity is θ(m). Consider the following program fragment written in a C like language:

counter = 0;
for (i = 1; i < = n; i++)
{ 
      if (A[i] == 1) 
         counter++;
      else {
         f(counter); 
         counter = 0;
      }
}

The complexity of this program fragment is

  1. A.

    Ω(n2)

  2. B.

    Ω(nlog n) and O(n2)

  3. C.

    θ(n)

  4. D.

    O(n)

Attempted by 306 students.

Sign up free to check your answer

Sign up free

Explore the full course: Zero To Hero

Loading lesson…