Q:

Order of growth of triple for loop

I'm practising algorithm complexity and I came across this code online but I cannot figure out the order of growth for it. Any ideas?
    int counter= 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++)
    counter++;

A:

Take it one step (or loop in this case) at a time:

The first loop increments i as long its square is lower than N, so this must be O(sqrt N), because int(sqrt(N)) or int(sqrt(N)) - 1 is the largest integer value whose square is lower than N;
The same holds for the second loop. We can ignore the 4 because it is a constant, and we do not care about those when dealing with big-oh notation. So the first two loops together are O(sqrt N)*O(sqrt N) = O(sqrt(N)^2) = O(N). You can multiply the complexities because the loops are nested, so the second loop will fully execute for each iteration of the first;
The third loop is obviously O(N^2), because k goes up to the square of N.

So the whole thing has to be O(N) * O(N^2) = O(N^3). You can usually solve problems like this by figuring out the complexity of the first loop, then the second, then the first two and so on.

