Common Complexity Scenarios

List of important complexities

In this lesson, we’ll study some common examples and handy formulas for solving time complexity problems. The following list shows some common loop statements and how much time they take to execute.

Simple for loop

for (int x = 0; x < n; x++)
    // statement(s) that take constant time

Running time complexity: $n = O(n)$.

Explanation: The C# for loop iterates through an array that contains integers from $0$ till $n-1$ ($[0, 1, 2, ..., n-1]$). During each iteration, x is assigned the value of the current number in the array. So, x is first $0$, then $1$, then $2$, …, then $n-1$. This means the loop runs a total of $n$ times; therefore, the running time complexity is $n$.

The for loop with increments of size $k$

for (int x = 0; x < n; x += k)
    // statement(s) that take constant time

Running time complexity: $2 + n(\frac{2 + c}{k})$ = $O(n)$.

Explanation: The initialization x = 0; runs once. Then, x gets incremented by k until it reaches n. In other words, x is incremented to $[0,{\space} k,{\space} 2k,{\space} 3k,{\space} \cdots, (mk) < n]$. Therefore, the incrementation part x += k of the for loop takes $floor(\frac{n}{k})$ time. The comparison part of the for loop takes the same amount of time and one more iteration for the last comparison. So, this loop takes $1 + 1 + \frac{n}{k} + \frac{n}{k}$ = $2 + \frac{2n}{k}$ time. The statements in the loop itself take $c × \frac{n}{k}$ time. Therefore, in total, $1 + 1 + \frac{2n}{k} + \frac{cn}{k}$ = $2 + n(\frac{2 + c}{k})$ times, which eventually gives us $O(n)$.