The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+21 votes
3.6k 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)$
asked in Algorithms by Veteran (358k points)
edited by | 3.6k views

3 Answers

+43 votes
Best answer
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)$
answered by Veteran (358k points)
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
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
+7 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.

answered by Loyal (8.5k points)
edited by
+5 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$
answered by (155 points)
edited by
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,771 questions
47,479 answers
145,663 comments
62,241 users