edited by
29,238 views
42 votes
42 votes

Consider the following function:

int unknown(int n){ 

int i, j, k=0; 
for (i=n/2; i<=n; i++) 
    for (j=2; j<=n; j=j*2) 
        k = k + n/2; 
 return (k); 

} 

The return value of the function is

  1. $\Theta(n^2)$      
  2. $\Theta(n^2\log n)$      
  3. $\Theta(n^3)$      
  4. $\Theta(n^3\log n)$
edited by

5 Answers

Best answer
86 votes
86 votes
The outer loop is running for $n/2$ times and inner loop is running for $\log_2 n$ times (each iteration doubles $j$ and $j$ stops at $n$ means $\log_2 n$ times $j$ loop will iterate).

Now in each iteration $k$ is incremented by $n/2$. So, overall $k$ will be added $n/2 \ast \log n \ast n/2$ with an initial value of $0$. So, final value of $k$ will be $\Theta(n^2 \log n)$.

Correct Answer: B.
edited by
17 votes
17 votes
here point to be noticed is complexity of returned value is asked but not the complexity of just execution code.so we just count how many times value of k is computed before completion of outer as well as inner loop.

outer loop executes n times

inner loop executes log n base 2 times and each time value of k is incremented by n/2

n/2 + n/2  +n/2..... till second loop executes.

this says after completion of inner loop value of k will be (logn)*n/2

And due to outer loop this calculation occurs for n times

So combining all we get total value as

n*n/2*log(n)

$n^{2}logn$
edited by
9 votes
9 votes

  Here we have to tell the value of k returned not the time complexity.

for (i  = n/2; i <= n; i++)
        for (j = 2; j <= n; j = j * 2)
            k = k + n/2;
    return k;

The outer loop runs n/2 times The inner loop runs logn times.(2^k = n => k = logn). Now looking at the value of k in inner loop, n is added to k, logn times as the inner loop is running logn times. Therefore the value of k after running the inner loop one time is n*logn. Therefore total time complexity is inner multiplied with outer loop complexity which (n for outer and nlogn for inner) n$^{2}$logn.

edited by
0 votes
0 votes

The above answer  is given By Sachin mittal sir ,

I only written this answer bcoz to clear confusion 

  1. first we can confuse that there is asking for the overall looop complexity but here clearly mentioned that we need to calculate the asymptotic valuie of $K$ i.e. returna value 
  2.  second place when we can confuse that we may be think that inner loop running $logn $ times so that the value of k will incerase $K$ ,  $ logn$ times but it is not correct bcoz in here $K$ is increament by the addition of $2 $ not in the addition of $j$
Answer:

Related questions

113 votes
113 votes
8 answers
3
Arjun asked Sep 24, 2014
27,876 views
The number of elements that can be sorted in $\Theta(\log n)$ time using heap sort is$\Theta(1)$$\Theta(\sqrt{\log} n)$$\Theta(\frac{\log n}{\log \log n})$$\Theta(\log n)...
34 votes
34 votes
4 answers
4
Arjun asked Sep 23, 2014
24,130 views
What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?$\theta(n^2)$ $\theta(n^2\log n)$ $\theta(n^3)...