Q:

Order of growth of the code below

What is the order of growth of the worst case running time of the following code fragment as a function of N? ￼
int sum = 0; 
for (int i = 0; i*i < N; i++) 
   for (int j = 0; j*j < 4*N; j++) 
       for (int k = 0; k < N*N; k++) 
           sum++;

A:

outer loop runs until i*i >= N, that means it runs total of
sqrt(N) times.
For each iteration of outer loop, inner loop runs until j*j >= 4*N, similarly that means it runs sqrt(4N) = 2sqrt(N) times.
For each iteration of middle loop, inner loop runs until k>=N*N, this means N^2 iterations.
Increasing sum is done in constant time.

Multiply the above because you do (3) for each iteration of (2), and (2) for each iteration of (1), and you get sqrt(N)*2sqrt(N)*N^2 = 2N^3, which is in O(N^3)

