Time complexity for loop with pow and log n advancement.

Question

So, I'm analyzing this loop. And I'm not sure of the time complexity.

int j = 2
while (j < n) {
  int k = j
  while (k < n) {
    Sum += a[k]*b[k]
    k += n^1/3 * log n
  }
  j = j*sqrt(5)
}

We have to loops, one with J and another with K. The J loop executes with a factor of increase of sqrt(5) that I'm sure we can say it will have a time complexity of O(log(n)). So the trick is about how many times the loop with k executes. We can appreciate that this variable increase n^1/3 * log n per loop. So that make me think that the time complexity of that loop is... probably greater than O(log(n)) but less than n. Because it's multiplying a very small number as it's log(n) with a pow of n... So my guess now is that the code is O(log(n) * log(n)). But I think we can calculate a more precise time complexity.

Anyone have some ideas of how to do it?

Answer 1

I think the trick is that the inner cycle (k) executes k * n^(1/3) * log (n) = n until the cycle breaks. So K = n^(2/3)/log(n) and because the outer cycle executes O(log n) then we can say that the overall time complexity is O(n^(2/3)).