What is the Big O of a For Loop, Iterated Square Root Times?

Question

I am trying to find the Big O for this code fragment:

for (j = 0; j < Math.pow(n,0.5); j++ ) {
 /* some constant operations */
}

Since the loop runs for √n times, I am assuming this for-loop is O(√n). However, I read online that √n = O(logn).

So is this for loop O(√n) or O(logn)?

Thanks!

Answer 1

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 body
• n is not modified in the loop body
• Math.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.)