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
    Koteswararao Pittala (anonymous)

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

    Koteswararao Pittala answered
      0
      Koteswararao Pittala (anonymous)

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

      Koteswararao Pittala answered
        0
        Madhav Purohit (anonymous)

        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

        Madhav Purohit answered
          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.

          Ashutosh Bhatia answered
            0
            Koteswararao Pittala (anonymous)

            thanx bro Ashutosh Bhatia

            Koteswararao Pittala answered
              Add image to editor add image from link

              Question stats

              • Active
              • Views555 times
              • Answers5 answers
              • Followers1 follower
              Question and answer is powered by AnsPress