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 (int x = 0; x < n; x++) {
    //statement(s) that take constant time
}

Running time Complexity = T(n) = $(2n+2) + cn = (2+c) n + 2$. Dropping the leading constants $\Rightarrow n + 2$. Dropping lower order terms $\Rightarrow O(n)$.

Explanation: C++ for loop increments the value x by 1 in every iteration from 0 till n-1 ([0, 1, 2, …, n-1]). So n is first 0, then 1, then 2, …, then n-1. This means the loop increment statement x++ runs a total of $n$ times. The comparison statement x < n ; runs $n+1$ times. The initialization x = 0; runs once. Summing them up, we get a running time complexity of the for loop of $n + n + 1 + 1= 2n+2$. Now, the constant time statements in the loop itself each run $n$ times. Supposing the statements inside the loop account for a constant running time of $c$ in each iteration, they account for a total running time of $cn$ throughout the loop’s lifetime. Hence the running time complexity is $(2n+2) + cn$.

For-loop with increments of size k

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

Runing 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 will be incremented to [$0, k, 2k, 3k, \cdots, (mk) < n$]. Hence, 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. While the statements in the loop itself take $c\times\frac{n}{k}$ ...