Time Complexity Analysis - Nested Loops - Inner Increments by sqrt(k)

Question

What is the time complexity of this algorithm:

j = 1
while (j < n) {
   k = j
   while (k < n){
      sum += a[k]*b[k]
      k += sqrt(k)
  }
  j += 0.25*n
}

Answer 1

Outer loop runs only 4 times. So, we could just start with the first iteration of the loop where k starts with 1.  Needs to get to n.  Then we could multiply the answer by 4, and that would be the worst case.

So, effectively, the question is:

// In this code, how many times does the while loop run?
k = 1
while (k < n){
    k += sqrt(k)
}

One can conclude that that only takes THETA(sqrt(n)) time, using two different arguments.

1. We claim that this must be OMEGA(sqrt(n)), because k needs to go from 1 to n, and it never increments by anything larger than sqrt(n).  Therefore, it must require at least sqrt(n) steps.
2. We claim that this must be BIG OH(sqrt(n)), because of the following:
   • Number of steps taken when k goes from n/4 to n is at most 2*sqrt(n) because square root of k is at least sqrt(n) / 2.
   • Similarly number of iterations of inner loop, when k moves from n/16 to n/4  =  sqrt(n), because square root of k is at least sqrt(n)/4.
   • Similarly for k to go from n/64 to n/16  =  sqrt(n) / 2
   • Summing up all together =  sqrt(n) * [ 2 + 1 + 0.5 + 0.25 + .... ]   <= 4*sqrt(n)

 

[Thanks to Piyush Gupta for his suggestion in simplification of big oh analysis.]