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

Best answer
87 votes
87 votes

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.

edited by
25 votes
25 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.
edited by
4 votes
4 votes
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)
edited by
3 votes
3 votes

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

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,946 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,288 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 $