# The complexity of this program fragment is

0

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)

Ravi Garg edited question

0
Ashutosh Bhatia (anonymous)

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.

0
Koteswararao Pittala (anonymous)

can anybody explain the best ,worst and average case complexity for the above problem with an example

0

Asymptotically calculating worst case complexity of this program can compared with that O(n^2) in worst case in best case it would be o(n) so here option d is matching

0
Koteswararao Pittala (anonymous)

can u give the example for this and explain it Madhav Purohit

0
Koteswararao Pittala (anonymous)

thanx bro Ashutosh Bhatia