Time complexity of a Function in c++

January 16, 2023

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