Asymptotic time complexity O(sqrt(n)log(n)n)

Question

for(int i=1; i*i <= n; i = i+1) {
   for(int j = n; j >= 1; j/4)   {
      for(int k = 1; k <= j; k=k+1) {
         f();
      }
   }
}

Why is the asymptotic complexity of this function O(n^{3/2})? I think, it should be O(sqrt(n)log(n)n). Is this the same to O(sqrt(n)n)? Then, it would be O(n^{3/2})..

• Outer loop is O(sqrt(n)).
• first inner loop is O(log(n)).
• second inner loop is O(n).

Answer 1

The outer two loops (over i and j) have bounds that depend on n, but the inner loop (over k) is bounded by j, not n.

Note that the inner loop iterates j times; assuming f() is O(1), the cost of the inner loop is O(j).

Although the middle loop (over j) iterates O(log n) times, the actual value of j is a geometric series starting with n. Because this geometric series (n + n/4 + n/16 + ...) sums to 4/3*n, the cost of the middle loop is O(n).

Since the outer loop iterates sqrt(n) times, this makes the total cost O(n^(3/2))