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 q(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)omega(n^2) (b) omega(nlogn) and O( n^2) (c) theta(n) (d) o(n)

First of all, the question us not spelled corectlly. Here q(m), is nothing but theta(m). This question is from GATE CS 2004. Lets take all one, in this case f(m) will not be called even once and therefore the complexity is theta(n). Now take all zero, in this f(m) will be called every time with parameter f(0), that nothing but theta(0), as given in the question. Here theta(0) is nothing but a constant which called n times and therefore the complexity is again theta(n). You can see the other case also apart from all zero and all 1, finally you find that the complexity is always theta(n). So as per this discussion the correct answer is C.