For-While Nested Loops Time Complexity - Inner Loop increments by n^1/3

Question

for (int j = 1 to n) {
  int k = j
  while (k < n) {
    Sum += a[k]*b[k]
    k += n^1/3
  }
}

For this one I came across the answer of O(n^2) but the answer key was n^5/3

Anyone can explain when we can ignore the constants? Thx

Answer 1

Hi Wenjun,

Let's take a look at the external loop first. For j, there is obviously n loops because it starts from 1 and increase by 1 every time until n.

Then internally, let's look inside at every loop of j. k = k + n^1/3, that is, k starts from j and increase by n^1/3 every time until n. We can suppose k = n when it stops (since it will only be 1 time more or less increment). How many times did k increase? Let it be x times. We have k + x*n^1/3 = n, so x = (n-k) / n^1/3 = n^2/3 - k / n^1/3.

This polynomial equation is the number of loops of k, for every j. The first element does not change for each j loop while the second does (as k starts from j for every j loop). Since we have n loops of j, so the total number of loops we have is actually

n*(n^2/3) - （1+2+3+...+n-1) / n^1/3

= n^5/3 - (n*(n-1)/2) / n^1/3

= n^5/3 - (1/2)*n^5/3 + (1/2)*n^2/3

Since every loop takes constant time here, we have the time complexity as:

= O((1/2)*n^5/3) = O(n^5/3)

BTW, I think using O() earlier is more convenient when we do it for ourselves.

Answer 2

1+2/3=5/3, 1is out loop 2/3 is in loop

Answer 3

I describe the answer in this way:

target: find out how many time will the most inner line run.

outer loop is quite clear, set the inner loop will run x times for each j.

then the question becomes when k will bigger than n (in another word: how many times it will run until k is bigger than or equal to n)?

that time could be expressed as x * (n^1/3 ) >= n    // core equation(personally, I call this)

so x >= n/(n^1/3)

thus x > = n^2/3        //

then we know that for each j, the most inner part will run at least n^2/3 times

so we got time complexity O(n^(2/3 + 1)) = O(n^5/3)

And for your question, for instance, f(n) = n^(1/3*2) can NOT equal to g(n) = n^(2) , that 1/3 can not be considered as a constant. It is an exponent.
All this kind of problem could be solved by solving that core equation to get the running time x.

Answer 4

Inner Loop:

k goes till n and increments by n^1/3 in every iteration
k, k+n^1/3, k+n^1/3+n^1/3 ...... k+(n^1/3)x

equating this to n, we get x = O(n^2/3)

Outer Loop:

j goes till n and increments by 1 with every iteration

Therefore, time complexity of the outer loop is O(n).

Time Complexity = n*n^2/3 = n^(1+2/3) = O(n^5/3).