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

Question

I am trying to find Big O for this piece of code:

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

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

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

Thanks!

Answer 1

A few assumptions need to be made, but the time complexity of this cycle seems to be O (√n). Assumptions:

• the body of the loop is executed in constant time regardless of the value of j .
• j does not change in the body of the loop
• n does not change in the body of the loop
• Math.pow(n,0.5) is performed in constant time (maybe it's true, but it depends on the specific Java Runtime Environment)

As noted in the comment, this also assumes that the initialization of the loop is j = 0 , not j - 0 .

Note that the loop would be much more efficient if it were overwritten:

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

(This is valid refactoring only if the body does not change n .)

Answer 2

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

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

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

[the youngest member of the amount is absorbed by another.]

The assumption P(n)=log(n) may be valid in the context of arbitrary precision integers, where at least O(log(n)) bits are required to represent the integer n . But this only makes sense for huge n values.