Time complexity of a Function in c-CodePudding

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

CodePudding user response：

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

CodePudding user response：

Your outer loop (i) has a complexity of O(n/2)

The middl-er loop (j) has a complexity of O(log(n))

The inner loop (k) has a complexity of O(n)

Has they are nested, the total complexity of the function in term of n is

(n/2) * log(n) * n = n² * log(sqrt(n)) which asymptotically, taking into account big-O notation gives O(n² * log(n))