PA of Algorithms Q39

39Let 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;
}
}
The complexity of this program fragment is

Option : C
Explanation :
Case I :– if A = 0 0 0 0 0 0 0 ...
then always else part is execute so f (wanter) where counter = 0 is executed n times.
As given in clvestion complexity of f(o) is O (1) So O (1) + O (1)..... b times ⇒ O (n)
Case II : if A = [1, 1,.................1]
the loop execute n time and only if statment is executed hence complexity is O (n).
Case III : if A = [1,0,1,0,1,0..........]
or A = [0,1,0,1,0,1...................]
or any other case.
Both if and else is executed but every time when else part is executed counter is again set to O. Hence complexity is O (n).

Forgot your password?

I agree with the Terms.