Common Complexity Scenarios

List of important complexities

The following list shows some common loop statements and how much time they take to execute.

Simple for-loop with an increment of size 1

for x in 0..n {
    //statement(s) that take constant time
}

Running time Complexity = T(n) = $O(n)$.

Explanation: Rust for in loop takes an iterator for the range 0…n. It calls iter.next() until the value returned by it is None, meaning the end of the range.

The constant statements inside also run n times. Making the time complexity cn,where c is the number of statements. Dropping the constant, the time complexity is $O(n)$.

For-loop with increments of size k

for x in (0..n).step_by(k){
   // statements(s) that take constant time
}

Runing Time Complexity = $n/k$= $O(n)$

Explanation: This where it gets a little tricky step_by() uses a fuction nth which utilizes advance_by() which internally runs a loop something like this.

for i in 0..k{
  self.next().ok_or(i)?;
}

Which makes the time complexity n but 0..n is a Range and it implements it’s own nth() function which is optimized and then we get the time complexity n/k which after eliminating constants we get to O(n).

Simple nested for-loop

for i in 0..n{
  for j in 0..m{
     // statements that take constant time
  }
}

Running Time Complexity = $nm(2+c)+2+4n =O(nm)$

Explanation: The inner loop is a simple for-loop that takes $(2m+2) + cm$ time, and the outer loop runs it $n$ times. So, it takes $n((2m+2) + cm)$ time. Additionally, the initialization, the increment, and the test for the outer loop take $2n+2$ time. In total, the running time is $n((2m+2) + cm)+2n+2 = 2nm+4n+cnm+2 = nm(2+c)+4n+2$, which is $O(nm)$.

Nested for-loop with dependent variables

for i in 0..n{
    for j in 0..i{
        //Statement(s) that take(s) constant time
    }
}

Running Time Complexity = $O(n^2)$

Explanation: The outer loop runs $n$ times and for each time the outer loop runs, the inner loop runs i times. The statements in the inner loop do not run at the first iteration of the outer loop since i is 0; then they run once at the second iteration of the outer loop since i is equal to $1$ at that point. Then they run twice, and then thrice until i is $n-1$. They run a total of $c + 2c + 3c + \cdots + (n-1)c$ times = $c\left(\sum_{i=1}^{n-1} i \right) = c\frac{(n-1)((n-1)+1)}{2} = \frac{cn(n-1)}{2}$. The initialization of j in the inner for-loop runs once in each iteration of the outer loop. This statement incurs a running time of $n$. In the first iteration of the outer for-loop, the test for the inner loop runs once. In the second iteration, it runs twice and so on. It incurs a total running time of $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$. In each iteration of the outer loop, the call to iter.next() runs one less time than the test for the inner loop. It accounts for a running time of $0 + 1 + 2 + \cdots + (n-1) = \frac{n(n-1)}{2}$. So in total, the inner loop has a running time of $\frac{cn(n-1)}{2} + \frac{n(n+1)}{2} +\frac{n(n-1)}{2}+n$.The outer loop set-up, testing against the range limit and calls to iter.next() account for a running time of $2n+2$. That means the entire script has a running time of $2n + 2 + \frac{cn(n-1)}{2} + n + \frac{n(n+1)}{2} +\frac{n(n-1)}{2}$, which is $O(n^2)$.

Nested for-loop with index modification

for mut i in 0..n{
    i*=2;
    for j in 0..i{
        // Statement(s) that take(s) constant time
    }
}

Running Time Complexity = $O(n)$

Explanation: Notice that the outer loop index variable is modified in the loop’s body. The first column in the following table shows the value of i immediately after entering the outer for-loop. The second column shows the modified value of i after the i*=2; statement is run.

Outer Loop	Inner Loop
i = 0	i = 0*2 = 0
i = 1	i = 1*2 = 2
i = 3	i = 3*2 = 6
$\cdots$	$\cdots$
i = $(n-1)$	i = $(n-1)\times2$ = 2(n-1)

A pattern is hard to decipher here. So, let’s simplify things. In the outer loop, i is doubled and then incremented each time. If you ignore the increment part, you will be slightly over-estimating the number of iterations of the outer for-loop. That is fine because you are looking for an upper bound on the worst-case running time (Big O).

If $i$ continues doubling, it will get from $1$ to $n-1$ in roughly $log_2{(n-1)}$ steps. With this simplification, the outer loop index goes (approximately) $1, 2, 4, \cdots, 2^{log_2(n-1)}$. We’ve ignored the iteration with $i=0$, but it wouldn’t affect the result in Big O. If you are interested, you can add $1$ to all the steps in the following calculations. This sequence can also be written as $2^0, 2^1, 2^2, \cdots, 2^{log_2{(n-1)}}$. This series also gives the number of iterations of the inner for-loop. Thus, the total number of iterations of the inner for-loop is: $2^0 + 2^1 + 2^2 + \cdots + 2^{log_2{(n-1)}} = 2^{log_2(n-1)+1}-1=2^{log_2{(n-1)}}2-1 = 2(n-1)-1 = 2n - 3$.

And, the running time of the inner for-loop is $2 (2n-3) + 2 + c(2n-3)$ where $c$ is the running time of the statements in the body of the inner loop. This simplifies to $2n(2+c)-3c-4$. The contribution from the initialization, test, and increment operations of the outer for-loop is $2log_2{(n-1)}+2$. T total running time is $2n(2+c)-3c-4+2log_2{(n-1)}+2$. The term “linear” in $n$ dominates the others, and the time complexity is $O(n)$.

Note that you could have done a rough approximation by saying that the outer loop runs at most $n$ times, and the inner loop iterates at most $n$ times each iteration of the outer for-loop. That would lead you to conclude that the total running time is $O(n^2)$. Mathematically, that is correct. But it isn’t a tight bound.

Loops with log(n) time complexity

let mut i = //constant
let n = //constant
let k = //constant
while (i < n){
    i*=k;
    // Statement(s) that take(s) constant time
}

Running Time Complexity = $\log_k(n)$ = $O(\log_k(n))$

Explanation: A loop statement that multiplies/divides the loop variable by a constant, such as the above takes $\log_k(n)$ time because the loop runs that many times. Consider an example where n = 16, and k = 2:

i	Count
1	1
2	2
4	3
8	4
16	5

$\log_k(n) = \log_2(16) = 4$

---