# 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.

## 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}$ 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 80+ hands-on prep courses.