Common Complexity Scenarios
This lesson includes a summary of the discussion on complexity measures. It also includes 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) = . Drop the leading constants . Drop 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]). x
is first 0, then it is 1, then it is 2, and …
Then finally it is 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, you 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; therefore 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. This loop takes time. The statements in the loop itself take time. In total, times, which eventually gives you .
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, the increment, and the test for the outer loop take time. 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. 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, and then thrice until i
is . They run a total of times = . The initialization of j
in the inner for-loop runs once in each iteration of the outer loop. 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. 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. It accounts for a running time of . So in total, the inner loop has a running time of . The outer loop initialization, the test and the 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 you ignore the increment part, you will be slightly over-estimating the number of iterations of the outer for-loop. That is fine because you are looking for an upper bound on the worst-case running time (Big O).
If continues 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: .
And, 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 . T total running time is . The term “linear” in dominates the others, and the time complexity is .
Note that you could have done a rough approximation by saying that the outer loop runs at most times, and the inner loop iterates at most times each iteration of the outer for-loop. That would lead you 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. Consider an example where n
= 16, and k
= 2:
i |
|
---|---|