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

**. This means that, according to the way data**

*n***is submitted in the input, the algorithm can execute or fail to execute some instructions.**

*n*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

**statement (within a repetition structure) creates possibilities for**

*if***execute or not execute**the statement on

**, depending on input data**

*line 5***.**

*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

**always executed, we have the**

*line 5***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

*to never be executed, we have the*

**line 5****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

**will never be executed.**

*line 5*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]*“**, “**// the instructions*int i=1*“, “*i<n.length*“, “*i++*“, “*if(n[i]>max)*“, “*max=n[i]*“, “*return max*“}**f(“***int max=n[0]*“) = 1 // quantity executed by 1st instruction**f(“**quantity executed by 2nd instruction*int i=1*“) = 1 //**f(“**quantity executed by 3rd instruction*i<n.length*“) = n //**f(“**quantity executed by 4th instruction*i++*“) = n-1 //**f(“**quantity executed by 5th instruction*if(n[i]>max)*“) = n-1 //

**f(“**quantity executed by 6th instruction*max=n[i]*“) = 0 //**f(“**quantity executed by 7th instruction*return max*“) = 1 //

**∑**_{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

**will be executed**

*line 5***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]*“**, “**// the instructions*int i=1*“, “*i<n.length*“, “*i++*“, “*if(n[i]>max)*“, “*max=n[i]*“, “*return max*“}**f(“***int max=n[0]*“) = 1 // quantity executed by 1st instruction**f(“**quantity executed by 2nd instruction*int i=1*“) = 1 //**f(“**quantity executed by 3rd instruction*i<n.length*“) = n //**f(“**quantity executed by 4th instruction*i++*“) = n-1 //**f(“**quantity executed by 5th instruction*if(n[i]>max)*“) = n-1 //

**f(“**quantity executed by 6th instruction*max=n[i]*“) = n-1 //**f(“**quantity executed by 7th instruction*return max*“) = 1 //

**∑**_{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

*. It is possible to observe how the performance of the algorithm behaves in both cases.*

**T(n)=4n**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- 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- and worst-case **T(n)** time complexity formulas for the **Bubblesort** algorithm.

1.public static void bublesort(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.