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

+1 vote
j = 1
while (j < n) {
   k = j
   while (k < n){
      sum += a[k]*b[k]
      k += sqrt(k)
  }
  j += 0.25*n
}
asked Jul 12 in Asymptotic Analysis by Baijun Xie AlgoStar (400 points)
edited Jul 12 by Amrinder Arora

1 Answer

0 votes
 
Best answer

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

answered Jul 12 by Amrinder Arora (206 points)
selected Jul 18 by Baijun Xie
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...