Advertisements
What will be the time complexity for this function, can someone explain?
void fun(int n) {
int i,j,k, count = 0;
for(i = n/2; i <= n; i++)
for(j = 1; j <= n; j = 2*j)
for(k = 1; k <= n; k++)
count++;
}
I am trying to find the time complexity for the given function. I think that second loop is O(n) but some said that it is O(log(n)).
>Solution :
The outer loop will perform n/2
iterations. On each of its iterations
the middle loop will perform log(n)
iterations, since on every step j gets multiplied by factor of 2.
On each of its iterations the inner loop will perform n
steps.
So complexity is O(n/2 * log(n) * n) = O(n^2 * log(n))
.