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

- All categories
- Asymptotic Analysis (22)
- D&C (9)
- Greedy (1)
- Dynamic Programming (7)
- Backtracking/DFS/BFS (2)
- Branch & Bound (2)
- Graph Theory (14)
- NP-Completeness (4)

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.

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

...