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(2n+2) + cn = (2+c) n + 2. Dropping the leading constants n+2\Rightarrow n + 2. Dropping lower order terms O(n)\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 nn times. The comparison statement x < n ; runs n+1n+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+2n + n + 1 + 1= 2n+2. Now, the constant time statements in the loop itself each run nn times. Supposing the statements inside the loop account for a constant running time of cc in each iteration, they account for a total running time of cncn throughout the loop’s lifetime. Hence the running time complexity is (2n+2)+cn(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(2+ck)2 + n(\frac{2+c}{k}) = O(n)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,,(mk)<n0, k, 2k, 3k, \cdots, (mk) < n]. Hence, the incrementation part x+=k of the for loop takes floor(nk)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+nk+nk=2+2nk1+1+\frac{n}{k}+\frac{n}{k} = 2 + \frac{2n}{k} time. While the statements in the loop itself take c×nkc\times\frac{n}{k} time. Hence in total, 2+2nk+cnk=2+n(2+ck)2 + \frac{2n}{k}+\frac{cn}{k} = 2 + n(\frac{2+c}{k}) times, which eventually give us O(n)O(n).

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