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))`

.