Reputation: 101
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
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
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