sqrt time complexity comparison

Question

Is this loop --

for(int i = 0 ; i < sqrt(number) ; i++)
{
    //some operations
}

faster than this --

int length = sqrt(number);
for(int i = 0 ; i < length ; i++)
{
    //some operations
}

I was getting TLE in a code in an online judge but when i replaced sqrt in loop with length i got it accepted.

Can u please point out the time complexity of the loop with sqrt considering number to be <=1000000000

Answer 1

The time complexity itself isn't different between the two loops (unless the complexity of sqrt itself is dependent on the number) but what is different is how many times you're computing the square root.

Without optimisation like the compiler automatically moving loop invariant stuff outside of the loop (assuming that's even allowed in this case since the compiler would have to check a lot of things to ensure they can't affect the result or side effects of the sqrt call), the following code will calculate the square root about a thousand times (once per iteration):

number = 1000000;
for(int i = 0 ; i < sqrt(number) ; i++) { ... }

However, this code will only calculate it once:

number = 1000000;
root = sqrt(number);
for(int i = 0 ; i < root ; i++) { ... }