edited by
20,024 views
66 votes
66 votes

Let $A[1,\ldots,n]$ be an array storing a bit ($1$ or $0$) at each location, and $f(m)$ is a function whose time complexity is $\Theta(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

  1. $\Omega(n^2)$

  2. $\Omega (n\log n) \text{ and } O(n^2)$

  3. $\Theta(n)$

  4. $o(n)$

edited by

13 Answers

0 votes
0 votes
If counter is 0 , then f(counter) will be O(0) = 0.

Therefore the worst case input will all 1 and at last single 0 that is (n-1) 1's followed by one 0.

In this case , counter will have value n-1, when 0 comes else statement will call f(n-1)= O(n-1)=O(n).

Hence answer is C, O(n)
0 votes
0 votes

In this code fragment, for each repetition of for loop, there are two possibilities:

1. condition in if construct will be satisfied i.e. A[i] is 1, then counter variable will be incremented through execution of counter++ statement. Here time complexity is ⊖(1) i.e. constant time.

2. else construct will be executed i.e. two statements will be executed. Two statements are: f(counter) , counter=0.

Statement counter=0 takes constant time i.e. ⊖(1). 

Time complexity of program is dependent on the time complexity of f(counter).

Let us consider the worst case, if A[] contains all 1 except last element i.e. first n-1 elements are 1 and last element is 0. Then for each 1, if construct will be executed which takes constant time. Total time for n-1 1's is n-1. For last element which is 0 , else construct is executed. And by that time counter take value n-1 for n-1 increments. Then f() will take time ⊝(n-1) = ⊝(n). Total time complexity of program in worst case = n-1 + ⊝(n) = n-1 + kn = ⊝(n).

Option c is the answer.

There is a gate question :

https://gateoverflow.in/1076/gate2004-82

0 votes
0 votes

Here we can take some possible cases . 

Case 1: 

When the array containing all 1's .

Then it will take O(n) to increment the counter to n from 0. 

Case 2:

When the array containing all 0's .

Then the else part only executed and  it will take  n*O(1)= O(n) . [ O(1) is taken for each 0's because its mentioned in question that f(m)=O(m). And for all the time f is called with counter value=0]

 

Case 3:

When first n-1 elements are 1's and last element is 0

Then it will take O(n-1) to increment the counter to n-1.  And for executing the last input 0 with counter value "n-1" will take O(n-1) . 

So total it will take only O(n).

 

Case 4:

When half of the array containing 1's and half of the array containing 0's.

First half takes O(n/2) to increment the counter to n/2 . 

For the first 0 in the second half it will take O(n/2) . Because now the counter value is n/2.

And then the "counter=0" is executed and counter value changed to 0. So, for the remaining (n/2-1) zero's  the "f" is called with counter value 0. So it will take ( n/2-1)*O(1) 

So total it will take O(n) only in all the 4 cases.

Case 5:

+++++++++++++++++++++++

It will take O(n^2) when ??

++++++++++++++++++++++++

Suppose if the "counter=0" was not there in the else part.

Then as mentioned in the 4th case,

For first half of 1's it will take O(n/2) .

For the remaining n/2 0's , it will take n/2*n/2 = O(n^2). Because there's no "counter=0" statement. So for n/2 0's "f" is called with counter value n/2.

Hope this helps :)

0 votes
0 votes

Please note that inside the else condition, f() is called first, then counter is set to 0.

Consider the following cases:

a) All 1s in A[]: Time taken is Θ(n) as
                  only counter++ is executed n times.

b) All 0s in A[]: Time taken is Θ(n) as
                  only f(0) is called n times

c) Half 1s, then half 0s: Time taken is  Θ(n) as
                  only f(n/2) is called once.
Answer:

Related questions

31 votes
31 votes
6 answers
1
Kathleen asked Sep 18, 2014
19,272 views
The time complexity of the following C function is (assume $n 0$)int recursive (int n) { if(n == 1) return (1); else return (recursive (n-1) + recursive (n-1)); }$O(n)$$...
42 votes
42 votes
4 answers
2
Kathleen asked Sep 18, 2014
11,956 views
Two matrices $M_1$ and $M_2$ are to be stored in arrays $A$ and $B$ respectively. Each array can be stored either in row-major or column-major order in contiguous memory ...
47 votes
47 votes
7 answers
3
Kathleen asked Sep 18, 2014
17,346 views
The recurrence equation$ T(1) = 1$$T(n) = 2T(n-1) + n, n \geq 2$evaluates to$2^{n+1} - n - 2$$2^n - n$$2^{n+1} - 2n - 2$$2^n + n $