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 formulalet 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)/6Is 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@AleksGpublic 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)
Time complexity of a triple nested loop with squared indices
algorithm analysis;runtime analysis;loops
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:$O(\sqrt n)$ for the first loop$O(\sqrt n - 1)$ for the second loop, which is the same as $O(\sqrt n)$, since the time complexity of 1 is constant.$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:The first on is, correctly, $O(\log n)$.The second one is just like in the first problem, so you get $O(\sqrt n)$.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)$.