Best case and worst case

Before reading this article, you must have already read the introductory article on algorithm analysis. If you haven’t read it yet, click here and check it out.

The terms best case and worst case are definitions used to describe the different possibilities of time complexity that the analysis of an algorithm can generate. It turns out that some algorithms, during their analysis process, can generate two different T(n) complexity functions. This article will address these aspects in detail.

How are cases defined?

Often the quantity of instructions q that an algorithm executes depends on the format of the input data n. This means that, according to the way data n is submitted in the input, the algorithm can execute or fail to execute some instructions.

Let’s take the findMax() algorithm as an example, a function that takes an array as a parameter and returns the largest value contained in this array:

1.public static int findMax(int[] n){
2.        int max = n[0];
3.        for(int i=1; i<n.length; i++){
4.                if(n[i] > max){
5.                        max = n[i];
6.                }
7.        }
8.        return max;
9.}

Note on line 4 that the conditional if statement (within a repetition structure) creates possibilities for execute or not execute the statement on line 5, depending on input data n.

4.if(n[i] > max){

It is usually in these conditional sections that the case definitions in algorithm analysis take place.

If, in all repetitions, the comparisons of line 4 return true, making the command of line 5 always executed, we have the worst case, as the maximum quantity of instructions will be executed and the algorithm will execute slower.

4.if(n[i] > max){ // always being true
5.        max = n[i]; // will always be executed
6.}

On the other hand, if, in all repetitions, the comparisons of line 4 return false, causing the command of line 5 to never be executed, we have the best case, since the minimum quantity of instructions will be executed and the algorithm will execute faster.

4.if(n[i] > max){ // always being false
5.        max = n[i]; // will never be executed
6.}

In this way, there is the definition of the best and worst case in the analysis of algorithms.

The tip is: if there is a conditional structure (if-else) inside a repetition structure, probably the execution of the algorithm will generate two complexity functions: T(n) of the best case and T(n) of the worst case.

What about the “average case”?

The average case is an open question for many programmers and computer scientists. It represents an estimate of how the algorithm will behave “on average”. For most situations, the average case analysis is not evident (Cormen et al., 2009) and requires probabilistic analysis techniques and randomized algorithms.

Such subjects are deeper in the field of mathematics and are outside the scope of our teaching objective for the time being. Therefore, we will not delve into the definition of the average case in this article. Especially because it doesn’t make much difference in an introductory approach to algorithm analysis.

Analysis of the findMax() algorithm

Let us now, in detail, perform the analysis of the findMax() algorithm and see the definition of the best and worst case.

1.public static int findMax(int[] n){
2.        int max = n[0];
3.        for(int i=1; i<n.length; i++){
4.                if(n[i] > max){
5.                        max = n[i];
6.                }
7.        }
8.        return max;
9.}

“Best case” analysis

The initialization of the variable “int max = n[0]” is an instruction that is executed only once;

2.int max = n[0]; // 1 time

initialization “int i=1” is an instruction that is executed only once;

3.for(int i=1; i<n.length; i++){ // 1 time

the quantity of “i++” increments in a for command is equal to the quantity of repetitions it executes, in this case, n-1 times (n-1 because the iterator i starts from the second position of the array, from index 1);

3.for(int i=1; i<n.length; i++){ // n-1 times

the quantity of executions of the comparison “i<n.length” is equal to the quantity of executions of the increment “i++” plus 1 (this 1 refers to the comparison that leaves the loop), totaling n times;

3.for(int i=1; i<n.length; i++){ // n times 

the quantity of executions of the conditional “if(n[i] > max)” is equal to the quantity of repetitions of the for in which it is contained, in this case, n-1 times. In the best case, the conditional will always be false.

4.if(n[i] > max){ // n-1 times and it will always be false

in the best case, the conditional of line 4 will always be false, and therefore the instruction “max=n[i]” of line 5 will never be executed.

5.max = n[i]; // will never be executed

finally, the function return statement on line 8 will only be executed once.

8.return max; // 1 time

After counting the algorithm instructions in the best case, the sum of all executions must be made. By mathematical definition this algorithm has:

• Q = { “int max=n[0]”, “int i=1”, “i<n.length”, “i++”, “if(n[i]>max)”, “max=n[i]”, “return max”} // the instructions
• f(“int max=n[0]”) = 1 // quantity executed by 1st instruction
• f(“int i=1”) = 1 // quantity executed by 2nd instruction
• f(“i<n.length”) = n // quantity executed by 3rd instruction
• f(“i++”) = n-1 // quantity executed by 4th instruction
• f(“if(n[i]>max)”) = n-1 // quantity executed by 5th instruction
• f(“max=n[i]”) = 0 // quantity executed by 6th instruction
• f(“return max”) = 1 // quantity executed by 7th instruction
• ∑_q∊Q f(q) = 1+1+n+(n-1)+(n-1)+1 = 3n+1 // cost of time complexity

In this way, it can be said that the time complexity of the findMax() algorithm in the best case is T(n)=3n+1.

“Worst case” analysis

The initialization of the variable “int max = n[0]” is an instruction that is executed only once;

2.int max = n[0]; // 1 time

initialization “int i=1” is an instruction that is executed only once;

3.for(int i=1; i<n.length; i++){ // 1 time

the quantity of “i++” increments in a for command is equal to the quantity of repetitions it executes, in this case, n-1 times (n-1 because the iterator i starts from the second position of the array, from index 1);

3.for(int i=1; i<n.length; i++){ // n-1 times

the quantity of executions of the comparison “i<n.length” is equal to the quantity of executions of the increment “i++” plus 1 (this 1 refers to the comparison that leaves the loop), totaling n times;

3.for(int i=1; i<n.length; i++){ // n times 

the quantity of executions of the conditional “if(n[i] > max)” is equal to the quantity of repetitions of the for in which it is contained, in this case, n-1 times. In the worst case the conditional will always be true.

4.if(n[i] > max){ // n-1 times and it will always be true

in the worst case, the conditional of line 4 will always be true and, therefore, the instruction “max=n[i]” of line 5 will be executed n-1 times.

5.max = n[i]; // n-1 times

finally, the function return statement on line 8 will only be executed once.

8.return max; // 1 time

After counting the algorithm instructions in the worst case, the sum of all executions must be made. By mathematical definition this algorithm has:

• Q = { “int max=n[0]”, “int i=1”, “i<n.length”, “i++”, “if(n[i]>max)”, “max=n[i]”, “return max”} // the instructions
• f(“int max=n[0]”) = 1 // quantity executed by 1st instruction
• f(“int i=1”) = 1 // quantity executed by 2nd instruction
• f(“i<n.length”) = n // quantity executed by 3rd instruction
• f(“i++”) = n-1 // quantity executed by 4th instruction
• f(“if(n[i]>max)”) = n-1 // quantity executed by 5th instruction
• f(“max=n[i]”) = n-1 // quantity executed by 6th instruction
• f(“return max”) = 1 // quantity executed by 7th instruction
• ∑_q∊Q f(q) = 1+1+n+(n-1)+(n-1)+(n-1)+1 = 4n // cost of time complexity

In this way, it can be said that the time complexity of the findMax() algorithm in the worst case is T(n)=4n.

Best and worst case graphical analysis

Let’s analyze the evolution of the number of instructions executed as a function of the input size n for the best case and worst case.

See the graph below that illustrates the results for T(n)=3n+1 and T(n)=4n. It is possible to observe how the performance of the algorithm behaves in both cases.

Both are linear functions and exhibit linear growth behavior, but it is possible to observe that the worst case will tend to execute more instructions for a given input value n.

The “worst case” role

By the terminology of the word, the term “best case” conveys the credibility of something important to consider. However, he is not the “star of the show”. In algorithm analysis, what really matters is worst-case analysis. The best case only reflects the best of situations in which an algorithm could run and, for that very reason, is not very important.

In real execution situations, nothing can be guaranteed about the performance of an algorithm, since you never know what types of data the algorithm will process. Therefore, the worst case sets an upper bound on the execution time. The worst case always guarantees that the performance of the algorithm will never be worse than it (it will never take longer than what was calculated). This gives us a guarantee of what to expect from the performance of the algorithm in the worst case scenario.

Exercises

To demonstrate that you have understood well the technique of “analysis by instructions counting” and the “formal mathematical definition” of the time complexity of an algorithm, solve the proposed exercises:

Exercise A

Using the instructions counting technique, find the best-case and worst-case T(n) time complexity formulas for the generic sorting algorithm.

1.public static void sort(int[ ] n){
2.        for (int i=0; i<n.length-1; i++) {
3.                for (int j=0; j<n.length-1; j++) {
4.                        if (n[j] > n[j+1]) {
5.                                int aux = n[j+1];
6.                                n[j+1] = n[j];
7.                                n[j] = aux;
8.                        }
9.                }
10.        }
11.}

Exercise B

Using the instructions counting technique, find the best-case and worst-case T(n) time complexity formulas for the Bubblesort algorithm.

1.public static void bubblesort(int[ ] n){
2.        for (int i=0; i<n.length-1; i++) {
3.                for (int j=0; j<n.length-1-i; j++) {
4.                        if (n[j] > n[j+1]) {
5.                                int aux = n[j+1];
6.                                n[j+1] = n[j];
7.                                n[j] = aux;
8.                        }
9.                }
10.        }
11.}

Continue your studies in this course and read the next article about “asymptotic behavior” in algorithm analysis.