Time complexity of a triple nested loop with squared indices

Question

I have seen this function in past year exam paper.

public static void run(int n){
    for(int i = 1 ; i * i < n ; i++){
        for(int j = i ; j * j < n ; j++){
            for(int k = j ; k * k < n ; k++){

            }
        }
    }
}

After give some example, I guess it is a function that with time complexity in following formula

let make m = n^(1/2)

[m+(m-1)+(m-2)+...+3+2+1] + [(m-1)+(m-2)+...+3+2+1] + ...... + (3+2+1) + (2+1) + 1

*Edit: I have asked this math question here, the answer is m(m+1)(m+2)/6

Is this correct, if no, what is wrong, if yes, how would you translate to big O notation. The question that I want to ask is not only about this specific example; but also how would you evaluate an algorithm, let's say, I can only give some example to watch the pattern it appears. But some algorithm are not that easy to evaluate, what is your way to evaluate using this example.

Edit: @LuchianGrigore @AleksG

public static void run(int n){
        for(int i = 1 ; i * i < n ; i++){
            for(int j = 1 ; j * j < n ; j++){
                for(int k = 1 ; k * k < n ; k++){

                }
            }
        }
    }

This is an example that in my lecture notes, each loop is with time complexity of n to the power of 1/2, for each loop there is another n^(1/2) inside, the total are n^(1/2) * n^(1/2) * n^(1/2) = n^(3/2). Is the first example the same? It is less than the second example, right?

Edit,Add:

How about this one? Is it log(n)*n^(1/2)*log(n^2)

for (int i = 1; i < n; i *= 2)
            for (int j = i; j * j < n; j++)
                for (int m = j; j < n * n; j *= 2)

Answer 1

For one of the loops, you've a complexity of $O(\sqrt n)$. You're nesting the loops three times, so you'll get the complexity of $O(\sqrt n^3)$, which is $O(n^{3/2})$.

If you want to be more precise, then for your original question, the complexity will be:

1. $O(\sqrt n)$ for the first loop
2. $O(\sqrt n - 1)$ for the second loop, which is the same as $O(\sqrt n)$, since the time complexity of 1 is constant.
3. $O(\sqrt n - 2)$ for the third loop, which is the same as $O(\sqrt n)$, since the time complexity of 2 is constant.

Therefore, the total complexity is still $O(\sqrt n^3) = O(n^{3/2})$.

EDIT/ADD:

You're pretty much correct, just make one more step to simplify the expression, remembering that $\log(n^2) = 2 \times \log(n)$. There are three loops:

1. The first on is, correctly, $O(\log n)$.
2. The second one is just like in the first problem, so you get $O(\sqrt n)$.
3. The third one is on the square of $n$, therefore you get $O(\log(n^2))$, which is the same as $O(2\log(n))$, which is the same as $O(\log(n))$.

Combining the three, it's pretty much like a multiplication, you will get: $O(\log(n) \times \sqrt n \times \log(n))$, which is $O(\log(n)^2 \times \sqrt n)$.