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.

However, upon nesting loops, the complexity changes considerably. Consider this (really bad) algorithm for comparing two lists:

let my_vec = vec![1,1,1,4,6,7,23,4];
let my_other_vec = vec![66,2,4,6,892];


for i in my_vec.iter() {
    for j in my_other_vec...