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

3 Answers

+47 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)$

Correct Answer: $B$
answered by Veteran (413k points)
edited by

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


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?

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


K=O(n^2 logn)

sir it is right ??
I think instead of having 1,2,3 in the coefficient it will be in the base of logn
+8 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 (9.3k points)
edited by
+7 votes
here point to be noticed is complexity of returned value is asked but not the complexity of just execution 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


answered by (185 points)
edited by
Outer loop should  execute n/2+1 times.

How it is n times?

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
49,808 questions
54,489 answers
74,659 users