Which is more efficient inside a loop condition, i

Question

Suppose for a given integer N, I need to run a loop square root of N times.

In C++, I can do it in these two ways like-

1)

long long sqrtN = std::sqrt(N);
for (long long i=1; i < sqrtN; i++) {
    // some piece of code
}

for (long long i=1; i * i < N; i++) {
    // some same piece of code
}

I found that std::sqrt() has O(logn) complexity. Also, I believe the multiplication of numbers is just a constant time operation.

So, it feels that the 2nd version is faster. But, for a very large value of n, that constant time in 2nd version may be significant.

Thus, I am not really sure which way is more efficient?

`sqrt` can be just a single assembly instruction, like [`sqrtsd`](https://www.felixcloutier.com/x86/sqrtsd). — Evg, Jun 22 '20 at 08:50
@Evg: ...which can still be very expensive. Number of assembly instructions isn't a good indicator for performance. — DevSolar, Jun 22 '20 at 08:51
@DevSolar, agree. The point was that `sqrt(n)` is not necessarily `O(log n)`. — Evg, Jun 22 '20 at 08:52
@Caduchon: No, not really. See [Is there a performance difference between i++ and ++i in C?](https://stackoverflow.com/questions/24886/is-there-a-performance-difference-between-i-and-i-in-c) — Fabio says Reinstate Monica, Jun 22 '20 at 11:23
@FabiosaysReinstateMonica yeah. But not for iterators. In this case it's the same. — Caduchon, Jun 22 '20 at 12:43

463035818_is_not_an_ai · Accepted Answer · 2020-06-22T08:56:30.223

I found that std::sqrt() has O(logn) complexity. Also, I believe the multiplication of numbers is just a constant time operation.

So far so good. You missed one detail. In the first you call sqrt once, in the second you compute i*i in each loop iteration. Hence it is actually O(log n) vs O(sqrt(n)), ie computing the bound outside of the loop wins because log n < sqrt(n).

To really know what is more efficient, the asymptotic complexity can only give you a first hint for what happens when you increase n up to infinity. For a real case you should look at the output of the compiler and profile.

I cannot stress enough that complexity is mainly of theoretical interest. For real code there is no way around profiling and measuring. It isn't unlikely that a O(N) algorithm wins over a O(logN) algorithm, because asymptotic complexity completely ignores any constant factors.

PS: Don't do premature optimization. Write code for readability and leave optimizations to your compiler. Only if you measured and found that too much time is spend for computing the bound of the loop you need to do something. Consider that i*i is a single instruction while the body of your loop is probably much more than that (cf. Amdahls law).

score 1 · Answer 2 · answered Jun 22 '20 at 08:53

I believe you have already answered most of your question yourself:

Calculating the square root of N has O(Log(N)) complexity
Calculating the square of i can happen quite fast, but you need to do it sqrt(N) times, and as a result the complexity is larger than O(sqrt(N)).

As O(Log(N)) is smaller than O(sqrt(N)), I would say that the first approach is the fastest.

score 0 · Answer 3 · answered Jun 22 '20 at 08:54

Think of it this way - calculating the square root only happens once. This time is essentially hidden when you execute the loop many times. The squaring, however, has linear complexity with the number of loop iterations, i.e. O(sqrt(N)), and will be slower for large N.

Which is more efficient inside a loop condition, i

3 Answers3