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) = . Dropping the leading constants . Dropping lower order terms .
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 times. The comparison statement x < n ;
runs times. The initialization x = 0;
runs once. Summing them up, we get a running time complexity of the for loop of . Now, the constant time statements in the loop itself each run times. Supposing the statements inside the loop account for a constant running time of in each iteration, they account for a total running time of throughout the loop’s lifetime. Hence the running time complexity is .
For-loop with increments of size k
for (int x = 0; x < n; x+=k) {
//statement(s) that take constant time
}
Runing Time Complexity = =
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 []. Hence, the incrementation part x+=k
of the for loop takes 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 time. While the statements in the loop itself take time. Hence in total, times, which eventually give us .
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.