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$. Drop the leading constants $\Rightarrow n + 2$. Drop 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]). x is first 0, then it is 1, then it is 2, and …

Then finally it is 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, you 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; therefore 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. 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}$ ...