The Complete Rust Programming Reference Guide

Loops

When in a loop, and the number of iterations is not known at compile time, it will be a major influence on runtime complexity. If an operation mentioned earlier is executed in the loop (for example, a sum operation), one could declare the complexity as O(1 * n) for the arithmetic operation. After adding another operation, we could express it as O(2 * n) and, while this would be correct, these are not the driving forces of the loop. Regardless of the number of operations that are executed n times, the main growth factor remains n. Hence, we simply say O(n), unless you are trying to compare the same algorithm, where the number of iterations actually makes a difference. If there are subsequent loops, the most expensive one is picked.