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)