edited by
19,994 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

2 votes
2 votes

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

1 votes
1 votes

ans of this always Q(n). 

best case also O(n).

worst case also O(n).

if all 1's then O(n) bcoz never enter into f(c). every time const.

if all 0's then O(n) bcoz every time const eventhough function call every time.

if half times 1's and half times 0's suppose n/2 times 1's so time is n/2 bcoz every time const.

after n/2 1's if 0 comes now count becomes n/2 so f(n/2) takes n/2 time and count becomes 0 immediately.

means whatever work he done until now this spoil(waste). now n/2 times 0's every time const so  time is n/2.

so total time becomes n/2+n/2+n/2=3n/2. means O(n).

so "c"  is ans.

if there is no counter =0 then n/2+n/2 times n/2 bcoz every time counter value is n/2 ,counter never decrease

so time=(n^2)/4

edited by
0 votes
0 votes

answer = option D

Consider the best case for this code snippet, for which test case is a string of all 1's
so, best case time complexity = $\mathcal{O}(n)$

for considering worst case for this code snippet, it has a variable time complexity, coz it depends on the function $f(m)$ whose time complexity is $\Theta(m)$
To show it has a variable time complexity, consider two cases to get the idea:

Case 1: $0\ 1 \ 0 \ 11 \ 0 \ 111 \ 0 \ 1111 \ 0 \dots$
in such a case the function behaves as some part of code snippet which has a linear increment i.e. time complexity of $\mathcal{O}(n)$

Case 2: $0\ 1 \ 0 \ 11 \ 0 \ 1111 \ 0 \ 11111111 \ 0 \dots$
in such a case the function behaves as code snippet which has a time complexity of $\mathcal{O}(n^2)$

but in case there are some constant number of 1's in between zeros it may also behave as of time complexity = $\mathcal{O}(1)$

Hence, for this code snippet we can say that $o(n)$ is a stronger option to choose. It covers all except the best case.

0 votes
0 votes
The key here is to see that counter can be incremented by maximum n times and the complexity of f depends upon counter.

Now if counter can contain maximum n,then it is not possible for f to have more than n complexity.

f can have one call taking n complexity ,or multiple calls whose combined complexity is n.

Consider that first we get x 1 and then 0 ,now f(x) will run till x,then we get y 1 followed by  0,now f(y) will run till y.

total elements x+y=n,so lop goes till n,

total time f executed =x+y

Min. f executes 0 and max. n.
--------------------------------------------------------------------------------------------------------------------

Also,note that if array contains all 1's then time would be thetha(n),and based on this we can reject A,B,D.
edited by
Answer:

Related questions

31 votes
31 votes
6 answers
1
Kathleen asked Sep 18, 2014
19,267 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,948 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,289 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 $