GATE CSE 2004 | Question: 82

Question

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

• A. $\Omega(n^2)$

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

• C. $\Theta(n)$

• D. $o(n)$

Comments

@ Ankit Chourasiya

Then why f(m) complexity is given .

---

For those who think we will have O(n^2) when the bit string is all ones and end element with 0.

Just remember in the last we should not multiply but add so it will be  n-1 + O(n-1)  i.e O(n)

---

i had the same doubt 

thanks @samir757

Answer 1

The key part in the code is "$\text{counter} = 0$" in the else part as we can see below.

Lets take the best case. This happens when $a[i] = 1$ for all $i$, and then the loop executes with time complexity $\Theta(1)$ for each iteration and hence overall time complexity of $\Theta(n)$ and we can say time complexity of the code fragment is $Ω(n)$ and hence options A and B are false.

Now, consider the worst case. This happens when $a[i] = 0$ or when else part is executed. Here, the time complexity of each iteration will be $\Theta(\text{counter})$ and after each else, counter is reset to $0$. Let $k$ iterations go to the else part during the worst case. Then the worst case time complexity will be $\Theta(x_1) + \Theta(x_2) + \dots +\Theta(x_k) + \Theta(n-k)$, where $x_i$ is the value of the counter when, $A[i] = 0$ and $f(\text{counter})$ is called.  But due to $\text{counter} = 0$ after each call to $f()$, we have,

$x_1+x_2+\ldots x_k = n-k.$ (counter is incremented $n-k$ by the “if” part)

$\implies \Theta(x_1) + \Theta(x_2) + \dots +\Theta(x_k) + \Theta(n-k) = \underbrace{\Theta(n-k)}_{\text{combined execution of f across all iterations}} + \underbrace{\Theta(k)}_{k \text{ times else part statement}} + \underbrace{\Theta(n-k)}_{n-k\text{ times if part}}$

$\qquad \qquad = \Theta(k) + \Theta(n-k) = \Theta(n)$.

Since the time complexity is $Ω(n)$ and $\Theta(n)$ we can say it is $\Theta(n)$ - Option (C). (Option D is false because the small o needs the growth rate to be STRICTLY lower and not equal to or lower as the case for big O)

If $\text{counter} = 0$ was not there in else part, then time complexity would be $\Omega(n)$ and $O(n^2)$ as in worst case we can have equal number of $0$'s and $1$'s in array $a$ giving time complexity $\Theta(1) + \Theta(2) + \cdots  + \Theta(n/2) + \Theta(n/2)$ would give $O(n^2)$. 

Correct Answer: C.

Comments

@samarpita @Abhrajyoti00 Is it fine now?

---

@gatecse yes sir

@Abhrajyoti00😀

---

if counter=0 not there then for worst case time complexity then array content will be like 101010… equal(alternate & equal 1 and 0).

Answer 2

 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.

Comments

one more case will be when (n-1) positions are 1 and One position(nth / last position) is 0.

In this case if condition will be executed n-1 times making the value of counter = n-1

when i = n then the else condition will be executed f (n - 1) once

therefore

T(n) = (n-1)*O(1) + 1*Q(n - 1) = O(n)

Now since best case and worst case are n therefore Option C is correct.

Answer 3

ans should be C which is Θ(n)

because in best case time complexity is Ω(n) when array contain all 1's then only if condition executing n times

in worst case time complexity is O(n)

let if condition  executing n/2 times then counter value is n/2 and "(n/2)+1" th iteration else condition executing so  f(n/2) executing n/2 times  and make counter value is 0 and again remaing (n/2) iterations running if condition (n/2) times so total time (n/2)+(n/2)+(n/2) so worst case time complexity is O(n)

Answer 4

I think best case time complexity when all of the array elements contains 1 , then it will be Ω(N) .

and in worst case time complexity when all of the array elements contains 0 . then it will be e(0)+e(0)+....+ e(0) (its totally depends upon the e(m) . )

or the array elemnt is like this 11111 to m000....  then time complexity 1+1+1......+e(m)+e(m)+....+ e(m) ( then also its totally depends upon the e(m) . )

Comments

I think your analysis in case of worst time complexity is wrong
because each time func(m)is invoked counter becomes 0 and as the
time complexity of fun(m)is O(m) and when counter would be zero then
the func would take O(0) time .
Worst time would be O(n).

---

no when function is called counter remains same , because the counter = 0 is after calling f(counter) so the counter remain same .

Answer 5

I think it actually depends upon the f(counter) function. what if f(0) is the terminating condition and takes constant time but if f(1) is called then it will take ø(m).

1.) Consider an Array A[5] = { 1,1,1,1,1 }

at index 0 : A[0] =1,then counter is incremented , counter = 1.

at index 1 : A[1] =1, then again counter is incremented, counter = 2.

..similarly counter = 5 at the end. Total Time complexity = constant for every element in this array, if there are N elements in the array and all are 1 then Time Complexity for such case - O(N).

2. )Consider an Array A[5] = { 0,0,0,0,0 } ( You might think this is the worst case but its not )

at index 0 : A[0] =0 ,then else part f(0) is called which takes constant time. because counter is already 0 intially and f(0) is the terminating condition as assumed above.

at index 1 : A[1] =0, then again else part f(0) is called which again takes constant time.

... and this continues till the end. Total time complexity  = constant for every element in this array, if there are N elements in the array and all are 0 then Time complexity for such case - O(N).

3.) Consider an Array A[5] = {1,1,0,0,0} 

at index 0: A[0] = 1, counter =1 takes constant time 'c'

at index 1: A[1] = 1, counter =2 takes constant time 'c'

at index 2: A[2] = 0, f(2) is called which takes ø(m) time. and then counter is set to 0 and  takes  ø(m) time

at index 3: A[3] = 0, f(0) is called which takes constant time 'c'

at index 4: A[4] = 0, f(0) is called which again takes constant time 'c'

Total Time complexity  = c + c + ø(m) + c + c = 4c + ø(m) . In case there are N elements where first few elements are 1's followed by continuous 0's. then for elements from starting upto all 1's in the array takes constant time and then for first 0 it takes ø(m) time and for the remaining 0's it takes constant time. Total time Complexity = c + c + c--- + c ( all 1's) + ø(m) ( first 0 encountered) + c + c + --- +c ( remaining 0's)   = (N-1)*c + ø(m) = which will be O(N) + ø(m) =  Max ( O(N) +O(m) )

4.) Consider an Array A[5] = { 1,0,1,0,1 }

at index 0: A[0] = 1, counter =1 takes constant time 'c'

at index 1: A[1] = 0, f(1) is called which takes  ø(m) time. and then counter is set to 0.

at index 2: A[2] = 1, counter = 1 takes constant time 'c'

at index 3: A[3] = 0, f(1) is called which takes ø(m) time. and then counter is set to 0.

at index 4: A[4] = 1, counter =1 takes constant time 'c'

Total time complexity = c + ø(m) + c + ø(m) + c = 3c + 2 * ø(m) =  Ceil(5/2) * c + Floor(5/2) * ø(m)

If there are N elements and the array consists of Alternate 1's and 0's then almost half of the elements will takes constant time and other half will call f(1) which takes ø(m). Total = (N/2)*c + (N/2) * ø(m) = O(N*m).

Hope it helps :)

please correct me if wrong :)

Comments

May I know why have you assumed O(m) time for function "f" always ?

I think f(m) takes time O(m) where m is the argument that is passed to it.Let O(m) be a place holder for a running time say am + b. Then in above case if f(2) is called then it will take time 2a+b.

So I think that in all cases time complexity is Θ(n).

Please correct me if I am wrong.

---

@ Vishal Rana, you're right. To state my interpretation,

Best case: If all are 1's: TC= n*O(1)= omega(n)

OR If all are zeroes: TC= n* theta(m). m in this case is 0, hence n*theta(0)= O(n)

Worst case (assume): If a sequence like [1,1,1,1,1,1,0,1,1,1,1,1,1]: TC= n/2*O(1) + 1*theta(n/2) + n/2*O(1)= O(n)+ O(n)+ O(n)= O(n)

As best and worst case, all have the same time complexity, answer= theta(n)

Please correct if this is wrong anywhere.

---

f(count) is inside for loop let the case {1,1,1,1,1,1,1,1...........1,0};

then count value is (n-1) and thenf(n-1)=theta(n-1).

f(n)=(n-1)(n-1)=n^2

---

you cant multiply like (n-1)(n-1) because for only last array value F(counter) will be called which will take Theta(n). It will be added but not multiplied Hence overall TC is Theta(n)

Answer 6

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 :)