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 x
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 .
Simple nested For-loop
for (int i=0; i<n; i++){
for (int j=0; j<m; j++){
//Statement(s) that take(s) constant time
}
}
Running Time Complexity =
Explanation: The inner loop is a simple for loop that takes time and the outer loop runs it times so it takes time . Additionally, the initialization, increment and test for the outer loop take time so in total, the running time is , which is .
Nested For-loop with dependent variables
for (int i=0; i<n; i++){
for (int j=0; j<i; j++){
//Statement(s) that take(s) constant time
}
}
Running Time Complexity =
Explanation: The outer loop runs times and for each time the outer loop runs, the inner loop runs i
times. So, the statements in the inner loop do not run at the first iteration of the outer loop since i
is 0 then; they run once at the second iteration of the outer loop since i
is equal to at that point, then they run twice, then thrice, until i
is . So, they run a total of times = . The initialization of j
in the inner for loop runs once in each iteration of the outer loop. So, this statement incurs a running time of . In the first iteration of the outer for loop, the j < i
statement runs once, in the second iteration it runs twice and so on. So, it incurs a total running time of . In each iteration of the outer loop, the j++
statement runs one less time than the j < i
statement, so it accounts for a running time of . So in total, the inner loop has a running time of . The outer loop initialization, test and increment operations account for a running time of . That means the entire script has a running time of which is
Nested For-loop With Index Modification
for (int i=0; i<n; i++){
i*=2;
for (int j=0; j<i; j++){
// Statement(s) that take(s) constant time
}
}
Running Time Complexity =
Explanation:
Notice that the outer loop index variable is modified in the loop’s body. The first column in the following table shows the value of i
immediately after entering the outer for loop. The second column shows the modified value of i
after the i*=2;
statement is run.
i = 0 |
i = 0*2 = 0 |
i = 1 |
i = 1*2 = 2 |
i = 3 |
i = 3*2 = 6 |
i = |
i = = 2(n-1) |
A pattern is hard to decipher here. So, let’s simplify things. In the outer loop, i
is doubled and then incremented each time. If we ignore the increment part, we will be slightly over-estimating the number of iteration of the outer for loop. That is fine because we are looking for an upper bound on the worst-case running time (Big O).
If keeps doubling, it will get from to in roughly steps. With this simplification, the outer loop index goes (approximately) . We’ve ignored the iteration with , but it wouldn’t affect the result in Big O. If you are interested, you can add to all the steps in the following calculations. This sequence can also be written as . This series also gives the number of iterations of the inner for loop. Thus, the total number of iterations of the inner for loop is: .
Therefore, the running time of the inner for loop is where is the running time of the statements in the body of the inner loop. This simplifies to . The contribution from the initialization, test, and increment operations of the outer for loop is . So, the total running time is . The term linear in dominates the others, and the time complexity is .
Note that we could have done a rough approximation saying that the outer loop runs at most times, the inner loop iterates at most times each iteration of the outer for loop. That would lead us to conclude that the total running time is . Mathematically that is correct, but it isn’t a tight bound.
Loops with log(n) time complexity
i = //constant
n = //constant
k = //constant
while (i < n){
i*=k;
// Statement(s) that take(s) constant time
}
Running Time Complexity = =
Explanation: A loop statement that multiplies/divides the loop variable by a constant such as the above takes time because the loop runs that many times. Let’s consider an example where n = 16, and k = 2:
i |
|
---|---|