# Common Complexity Scenarios

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

## List of important complexities

In this lesson, we are going to study some common examples and handy formulas for solving time complexity problems.

The following list shows some common loop statements and how much time they take to execute:

$$$$

### Simple for loop

```
for x in range(n):
# statement(s) that take constant time
```

**Running time complexity** = $n$ = $O(n)$

**Explanation**: Python’s `range(n)`

function returns an array that contains integers from 0 till n-1 ([0, 1, 2, …, n-1]). The `in`

means that `x`

is set equal to the numbers in this array at each iteration of the loop sequentially. So n is first 0, then 1, then 2, …, then n-1. This means the loop runs a total of $n$ times, hence the running time complexity is $n$.

$$$$

### For loop with increments

```
for x in range(1,n,k):
# statement(s) that take constant time
```

**Running time complexity** = $floor(\frac{n}{k})$ = $O(n)$

**Explanation**: With this Python statement, `x`

is initially set equal to 1 and then gets set to values incremented by `k`

until it reaches a number greater than or equal to `n`

. In other words, `x`

will be set to [$1, 1+k, 1+2k, 1+3k, \cdots, (1+mk) < n$]. It takes $floor(\frac{n}{k})$ time since there are that many numbers that `x`

is set to. Also, note that in Python, changing the value of `x`

within the loop would not affect the time complexity since `x`

is *initialized* at every iteration unlike in other languages such as C++ where `x`

is simply incremented/decremented/multiplied/divided. Try it for yourself!

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