One has to make several assumptions, but the time complexity of this loop appears to be O(√n). The assumptions are:
- the loop body executes in constant time regardless of the value of
j
. j
is not modified in the loop bodyn
is not modified in the loop bodyMath.pow(n,0.5)
executes in constant time (probably true, but depends on the specific Java execution environment)
As a comment noted, this also assumes that the loop initialization is j = 0
rather than j - 0
.
Note that the loop would be much more efficient if it was rewritten:
double limit = Math.pow(n, 0.5);
for (j = 0; j < limit; j++ ) {
/* some constant operations */
}
(This is a valid refactoring only if the body does not change n
.)