CODEWITHSUNDEEP
algorithmtime-complexity
Sanjay Verma
Sanjay Verma

Reputation: 101

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 Θ(n^2logn).

My doubt: The time complexity of the function is Θ(nlogn) which i don't understand how it can be Θ(nlogn) because outer loop will execute exactly n/2 times and inner loop will execute logn times.

How time complexity is different than return value of this function, can someone explain me in simple language so i can visualize it.

Upvotes: 0

Views: 86

Answers (2)

aakash250798
aakash250798

Reputation: 13

The function is having 2 loops i and j. i is being incremented from n/2 to n.So i will execute n-n/2+1 times. For j the loop starts from 2 and ends at n,and it is being incremented exponentially ,ie 2 then 4,8...upto logn times.So for this the no of iterations are logn+1 times. For every iteration in j there is an increment in k of n/2,so overall sum ie its return value.,which O(n^2logn). and overall time complexity is O(nlogn),for it has to execute the statement this many times.

Upvotes: 0

Paul Hankin
Paul Hankin

Reputation: 58409

The time the function takes (as counted by the number of loop iterations) is approximately (n/2) * (lg n).

For each iteration, k is incremented by n/2.

So the time complexity is O(n lg n) and the return value of the function is n/2 times larger, or O(n^2 lg n).

Upvotes: 3

Related Questions