# Common Complexity Scenarios

This lesson summarizes our discussion of complexity measures and includes some commonly used examples and handy formulae to help you with your interview.

We'll cover the following

## 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}$ time. Hence in total, $2 + \frac{2n}{k}+\frac{cn}{k} = 2 + n(\frac{2+c}{k})$ times, which eventually give us $O(n)$.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.