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: Java for loop increments the value x by 1 in every iteration from 0 until 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
}

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, 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. The statements in the loop itself take $c\times\frac{n}{k}$ ...