Clever Geek Handbook

Sqrt time complexity comparison

This cycle -

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 code in online judge, but when I replaced sqrt in a loop with length I got it.

Can you specify the time complexity of the loop using sqrt given number to be <=1000000000

+3


source to share


3 answers


By itself, the time complexity is not different between the two loops (unless the complexity itself sqrt

depends on the number), but that differs from how many times you calculate the square root.

Without optimization, like a compiler automatically moving the invariant elements of the loop outside of the loop (assuming that is even allowed in this case, since the compiler will have to check a lot of things to ensure they cannot affect the result or side effects sqrt

), the following code will compute 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 once:

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


source


The problem is that the entire expression has i < sqrt(number)

to be re-evaluated in the original code, and sqrt

is evaluated only once in the modified code.



Well, recent compilers can usually optimize for a loop, so it sqrt

only evaluates once before the loop, but do you want to rely on them?

+4


source


The first version forces the compiler to generate code that executes sqrt(number)

each time the condition is checked (as many times as it loops).

The second version only calculates the length once (one call sqrt

).

+2


source






More articles:


All Articles