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

algorithm, big-o, computer-science, java

Solution

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

Problem

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!

Original source