3.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 | 3.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)$
edited by
+21

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

+4
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
+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.

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$
edited

1
2