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)

• Raphael: What is the actual question here? Please restrict your self to one question.
• vonbrand: Each of the loops runs $\sqrt{n}$ times, for a total of $O(n^{3/2})$
• gnasher729: The last example is likely not doing what the thread starter thinks it does, and has complexity of O ((log n)^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)$.

• Timeless: Edited, Sorry but I agree that first loop is O(n^(1/2)), but the 2nd & 3rd loop are not start from 1, but i & j. Is it still the same?
• Aleks G: @null Yes, you still will receive the same overall O-complexity. See my edit
• brimborium: @null The reason behind this is the following: Let's say we have only two nested loops. The inner loop starts at 1 for the first iteration of the outer loop, at 2 for the second iteration, ..., at sqrt(n) for the last iteration of the outer loop. So on average, it starts at around sqrt(n)/2 and ends at sqrt(n), which makes it O(sqrt(n)/2)=O(sqrt(n)) (the same as the outer loop).
• Timeless: @AleksG since I have asked so many, would you mind to take a look at the added one, is it correct?
• Timeless: @brimborium thanks, only care about the one with significant performance affect. so O(N^3+N^2+N) = O(N^3), right? Would you mind to take a look at the added example. Is my answer correct?