0
counter = 0;
for (i=1; i<=n; i++)
if (a[i] == 1){
counter++;
} 
else {
f (counter); 
counter = 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 θ(m).

Then, What is the time complexity of this program fragment ?

I am stuck in the part that what will be the time complexity of function f(0),as it will be called continuously if array contains all the zeroes .

Barry
  • 9
  • 1
  • 5

1 Answers1

0

The code is always Theta(N). Let's say f(m) has cost cm for some constant c. Really one should do upper and lower bound analysis with two different constants since f(m) is Theta(m), but the analysis will be more or less the same.

Then, f is called with some sequence of values, x1, x2, x3, ..., xk which correspond to runlengths of 1s. The total cost of calling f is c*x1 + c*x2 + ... + c*xk = c(x1 + x2 + ... + xk). Since (x1 + x2 + ... + xk) is the total number of 1s in the array, this sum is at most N (the length of the array). So the total cost of calling f will always be O(N).

The code always loops N times, so N is also a lower bound for the total cost.

We've shown linear upper and lower bounds, and so f is Theta(N).

Paul Hankin
  • 54,811
  • 11
  • 92
  • 118
  • Thanks !! Just a doubt "What if counter = 0 is removed", then how TC will change ? – Barry Apr 14 '17 at 13:26
  • If you have a doubt about how to compute the variant problem, then you could try some example arrays and see what results you get. For example, all ones, all zeros, or alternating 1s and 0s. – Paul Hankin Apr 14 '17 at 13:30