4.7k views

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 | 4.7k views

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 * log n * n/2$ with an initial value of $0$. So, final value of $k$ will be $\Theta(n^2 log n)$

Correct Answer: $B$
answered by Veteran (406k points)
edited
+24

Return value is O(NlogN)
Time complexity of Program is N logN right !!?

+5
yes.
–2

why time complexity O(N log N)? it will be O(N2 log N) right? because no of time addition occurs also be counted . right?

+3
each addition take O(1) time ,so it will not affect the final time complexity
–2
if u have any source to say addition time is O(1) . Plz give the link
+1
Each addition is O(1).
+1
k<=logn+2 logn+3 logn+----n/2 logn

k<=logn(1+2+3+4---n/2)

K=O(n^2 logn)

sir it is right ??
0
I think instead of having 1,2,3 in the coefficient it will be in the base of logn

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.

answered by Loyal (9.3k points)
edited
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$
answered by (185 points)
edited
0
Outer loop should  execute n/2+1 times.

How it is n times?

1
2