Example 1: Measuring Time Complexity of a Single Loop Algorithm

A for Loop with n iterations

Now, consider what happens when a loop is involved. Consider the following Rust program:

Count the number of primitive operations in the above program.Go to lines 2 and 3 where variable initialization are taking place. They account for one primitive operation each.

Line 4 is a loop statement. This is a k for in construct that generates values between 0 (inclusive) and n (exclusive). for in is syntactic sugar to iterate over anything that implements the IntoIterator trait. Without going into the primitive operations used to implement the for in construct, we simply note that this loop runs n times.

for loop_variable in iterator {
    code()
}

expands to

{
    let result = match IntoIterator::into_iter(iterator) {
        mut iter => loop {
            let next;
            match iter.next() {
                Some(val) => next = val,
                None => break,
            };
            let loop_variable = next;
            let () = { code(); };
        },
    };
    result
}

You can read more about for ...