arrays - What is the time complexity of this program fragment? -

counter = 0; (i=1; i<=n; i++) if (a[i] == 1){ counter++; }  else { f (counter);  counter = 0;} } 

---

let a[1, …, n] array storing bit (1 or 0) @ each location, , f(m) function time complexity θ(m).

then, time complexity of program fragment ?

---

i stuck in part time complexity of function f(0),as called continuously if array contains zeroes .

the code theta(n). let's f(m) has cost cm constant c. 1 should upper , lower bound analysis 2 different constants since f(m) theta(m), analysis more or less same.

then, f called sequence of values, x1, x2, x3, ..., xk correspond runlengths of 1s. total cost of calling f c*x1 + c*x2 + ... + c*xk = c(x1 + x2 + ... + xk). since (x1 + x2 + ... + xk) total number of 1s in array, sum @ n (the length of array). total cost of calling f o(n).

the code loops n times, n lower bound total cost.

we've shown linear upper , lower bounds, , f theta(n).