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 = nn = O(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 nn times, hence the running time complexity is nn.

For loop with increments

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

Running time complexity = floor(nk)floor(\frac{n}{k}) = O(n)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,,(1+mk)<n1, 1+k, 1+2k, 1+3k, \cdots, (1+mk) < n]. It takes floor(nk)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.