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.)

Answer 2

Assuming the cost of the pow operation to be O(P(n)) for some function P, the global cost of the loop is O(√n.P(n)). If the pow call is taken out of the loop and performed only once, the cost is expressed as O(√n+P(n)).

In case P(n)=1, this gives respectively O(√n) and O(√n).

In case P(n)=log(n), this gives O(√n.log(n)) and O(√n).

[The lower order term of the sum is absorbed by the other.]

The assumption P(n)=log(n) could be valid in the context of arbitrary precision integers, where the representation of an integer n requires at least O(log(n)) bits. But that makes sense for huge values of n only.