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). 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;}
}
I am only able to deal with the best case where all the bits are 1 ,hence the time complexity will be Θ(n),but I am having confusion in determining worst case which will occur when all bits are either 0 or more than half of the bits are 0 , issue is the complexity of the function is confusing me ,if I try to ignore it then complexity will be Θ(n) itself ,please guide me in solving this .
The sum of all the counters passed to f is at most n, so the total cost in calling f is O(n). That's because f(m) has time complexity Theta(m), which implies cost f(m) < c*m for some c, so one can bound the cost of calling f with inputs m_1, m_2, ..., m_k by c*(m_1 + m_2 + ... + m_k).
There's some work done each time round the loop, so the total cost is also bounded below by a multiple of n. Therefore the total cost is Theta(n).