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
- A.
Ω(n2)
- B.
Ω(nlog n) and O(n2)
- C.
θ(n)
- D.
O(n)
Attempted by 306 students.
Sign up free to check your answer
Sign up freeLoading lesson…

