Algorithm analysis: how do you do it?

Learn how to do algorithm analysis. See examples and step-by-step demonstrations of analyzes performed on real algorithms.

Purpose of algorithm analysis

Algorithm analysis is an important discipline of Computer Science. It aims to provide more assertive methods for measuring algorithm performance.

As simply and directly as possible, algorithm analysis can be easily performed by empirical methods (based on practical experience), such as the time in seconds it takes to process an input. You could measure the elapsed time before and after the execution of an algorithm and, based on this result, infer about its performance.

The code below illustrates an example of this method of empirical time calculation using the Java language. It measures the execution time of the algorithm that calculates the nth term of the Fibonacci sequence (lines 15-18).

1.public static void main(String[] args) {

2.     int n;

3.     long start, end;

4.     double cpu_time_used;

5.     Scanner sc = new Scanner(System.in);

6.     System.out.println("Enter the nth term of the Fibonacci sequence");

7.     n = sc.nextInt();

8.     start = System.nanoTime();

9.     int result = fib(n);

10.     end = System.nanoTime();

11.     cpu_time_used = (double)(end-start) / 1_000_000_000.00;

12.     System.out.println("The "+n+"º Fibonacci term = "+result);

13.     System.out.println("Runtime was "+cpu_time_used+" seconds.");

14.}

15.public static int fib(int n) {

16.     if(n==2 || n==1)

17.          return 1;

18.     return fib(n-1) + fib(n-2);

19.}

In line 8 the initial time stamp is obtained in nano seconds. Line 9 calls the fib() function, which executes the Fibonacci algorithm. In line 10 the final time stamp is obtained, also in nano seconds. In line 11 the execution time is calculated. Finally, on line 13, the runtime is displayed.

Below are the execution times (in seconds) for some entries of this algorithm:

  • n=40: execution time around 0.4 seconds
  • n=41: execution time around 0.8 seconds
  • n=42: execution time around 1.2 seconds
  • n=43: execution time around 2 seconds
  • n=44: execution time around 3.1 seconds
  • n=45: execution time around 5 seconds

However, this is not the best way to perform algorithm analysis. These results were generated with the algorithm written in the Java language using the Eclipse IDE on an Intel Core i7 notebook. If these specifications changed, the results would surely be different.

Thus, the execution time of an algorithm can be influenced by several factors, such as: computer processing speed, programming languages used, compilers, operating system, to name a few.

These factors invalidate the reliability of performance results because the processing time of the algorithm can never be accurately known.

The analytical method for algorithm analysis

The analytical method is a more assertive way to perform algorithm analysis. It is not intended to calculate execution time in seconds, minutes or some other actual representation of time. It aims to find a mathematical expression to translate performance into “number of steps”. In this way, the algorithm performance can be measured totally independent of programming languages, compilers, tools and other physical factors that could invalidate the analysis.

Therefore, the RAM (Random Access Machine) model is the strategy used to measure performance analytically. It counts the steps an algorithm performs and ignores all aspects of processing speed, programming language, or any other type of hardware optimization. In this model, each operation consumes a constant and single computational cost.

Below are several examples of computational operations commonly found in algorithms, all at the same computational cost:

Value assignment

1.int value = 0; // a single computational cost

2.float sal = 2005.15; // a single computational cost

Value increment or decrement

1.value++; // a single computational cost

2.value--; // a single computational cost

Complex mathematical operations

1.value*(4/Math.sqrt(9)); // a single computational cost

Arrays element access

1.list[i]; // a single computational cost

Logical operations

1.if(value > 10); // a single computational cost

2.if(value==3 || value==2); // a single computational cost

Read and write operations

1.System.out.println("Hello World!"); // a single computational cost

2.scanner.nextInt(); // a single computational cost

Obviously, these instructions actually have significant differences in performance. Some are obviously faster to execute than others. However, as we are interested in analyzing algorithm performance based on the number of steps, the RAM model ignores such differences. Mainly because they have more to do with computers than with the algorithm itself.

Step count algorithm analysis

By quantifying the steps generated by the RAM model we can compare various algorithms with each other and more accurately state which one is faster, because, regardless of the speed of the computers on which they are executed, an algorithm that performs fewer steps will always be more fast for large volumes of processed data.

Below is a code from a simple program that we will use as an example to begin explaining the analytical technique of step counting. To perform this process, simply count, line by line, the amount of instructions performed by each command:

Algorithm

1.Scanner sc = new Scanner(System.in); // object creation = 1 instruction

2.int age; // variable declaration = 1 instruction

3.System.out.println("Enter your age:"); // write operation = 1 instruction

4.age = sc.nextInt(); // read and assign operation = 2 instructions

5.if (age >= 18) // logical operation = 1 instruction

6.     System.out.println("Adult:"); // write operation = 1 instruction

7.else

8.     System.out.println("Minor:"); // write operation = 1 instruction

Thus, we have that the algorithm performs a total of 7 instructions (the if-else are mutually exclusive). We say that T(n)=7 is the time complexity formula of this algorithm which, being a constant function, has constant complexity.

Analysis of linear algorithms

The analysis performed earlier was very easy and served only for learning. Let’s look at a more complicated example. An algorithm that, given an A[ ] array of n values, prints all the elements of that array.

Algorithm

1.public static void printArray(int[] A){

2.     for(int i = 0; i < A.length; i++){

3.          System.out.println(A[i]+"\n");

4.     }

5.}

Let’s dissect line by line the count of this algorithm:

2.for(int i = 0; i < A.length; i++){ // 1 initialization, n + 1 comparisons and n increments = 2n + 2 instructions

3.System.out.println(A[i]+"\n"); // n write operations = n instructions

Therefore, the algorithm performs a total of (2n+2)+n = 3n+2 instructions. We say that T(n)=3n+2 is the time complexity formula of this algorithm which, being a function of the 1st degree, has linearcomplexity.

Let’s go into the analysis of a slightly more complicated algorithm. An algorithm that, given an A[ ] array of n values, computes the largest value of that array. Note that the algorithm has a “for”repeating structure (lines 3-7) that performs an “if” conditional (line 4) n-1 times.

Algorithm

1.public static int findMax(int[] A){

2.     int max = A[0];

3.     for(int i =1; < A.length; i++){

4.          if(max < A[i]){

5.               max = A[i];

6.          }

7.     }

8.     return max;

9.}

Let’s dissect line by line the count of this algorithm:

2.int max = A[0]; // array access and assignment = 2 instructions

3.for(int i =1; < A.length; i++){ // 1 initialization, n comparisons and n-1 increments = 2n instructions

4.if(max < A[i]){ // n-1 logical operations = n-1 instructions

8.return max; // 1 value return = 1 instruction

Now realize that the amount of assignment instructions (in line 5) is very difficult to predict. We do not know when the conditional on line 4 will return true, as this depends on the structure of the information present in the arrangement A[ ]. It depends as follows:

  • If arrangement A[ ] is sorted in ascending order, the largest element will be the last one, so line 5 will be executed n-1 times (Worst case).
  • If arrangement A[ ] is sorted in descending order, the largest element will be the first one, so line 5 will never be executed (Best Case).

From this analysis we have that the algorithm will have two time complexity formulas:

  • In the worst case complexity will be: (2) + (2n) + (n-1) + (1) + (n-1) = T(n)=4n+1
  • In the best case the complexity will be: (2) + (2n) + (n-1) + (1) = T(n)=3n+2

Basically, the best case is when the algorithm receives the data as best it can for maximum performance. Similarly, the worst case is when the algorithm receives the worst possible data, and therefore has its worst performance.

It is extremely important to describe the concept of best and worst case in the algorithm analysis process since we can never predict the state of the data inputs that will be processed by the algorithm.

For this reason, we will ignore the “best case” concept and will always focus on doing the analysis always considering the “worst case”, because in this way we can guarantee that we will calculate the algorithm’s maximum time complexity formula. That is, its maximum execution time.

Quadratic algorithm analysis

Let us now move on to the analysis of a more complex algorithm. An information sorting algorithm that uses the famous bubble method: the Bubble Sort.

This algorithm is much more complex than the previous one because it is a quadratic algorithm. The term “quadratic” means that its complexity formula is a function of the 2nd degree at “worst case”.

But let’s do the analysis to see how this happens in practice.

Algorithm

1.public static void bubbleSort(int[] A) {

2.     boolean changed;

3.     do{

4.          changed = false;

5.          for(int j = 0; j < A.length-1; j++) {

6.               if(A[j] > A[j+1]) {

7.                    swap(A, j, j+1);

8.                    changed=true;

9.               }

10.          }

11.     } while(changed==true);

12.}

Worst case algorithm analysis

The Bubble Sort algorithm has the worst case when the A[ ] array is inversely ordered (when the array elements are in descending order).

2.boolean changed; // variable declaration = 1 instruction

4.changed = false; // 1 assignment (which occurs n times because it is inside a loop) = n instructions

5.for(int j = 0; j < A.length-1; j++) { // 1 initialization, n comparisons and n-1 increments, n times = 2n2 instructions

6.if(A[j] > A[j+1]) { // n-1 logical operations, n times = n2-n instructions

7.swap(A, j, j+1); // n-1 swaps, n times = n2-n instructions

8.changed=true; //n-1 assignments, n times = n2-n instructions

11.while(changed==true); // n logical operations = n instructions

Note that we consider that the repeatition structures “do-while” (lines 3-11) and “for” (lines 5-10) will always be executed. That is, we consider the worst case of executing the Bubble Sort algorithm.

Therefore, the sum of its instructions is equal to: 1 + n + 2n2 + 3 (n2-n) + n. By reducing this expression, we have that the algorithm performs a total of 5n2-n + 1 instructions. We say that T(n)=5n2-n+1 is the time complexity formula of this algorithm which, being a function of the 2nd degree, has quadratic complexity in the worst case.

But it turns out that the Bubble Sort algorithm has a particularity about the “do-while” repetition structure (lines 3-11). When arrangement A[ ] is already ordered (best case), no changes occur and the “do-while” loop is executed only once! This means that we have for the “best case” another time complexity formula. Let’s do this analysis.

Best case algorithm analysis

2.boolean changed; // variable declaration = 1 instruction

4.changed = false; // 1 assignment (which occurs only 1 time, because the arrangement is already sorted) = 1 instruction

5.for(int j = 0; j < A.length-1; j++) { // 1 initialization, n comparisons and n-1 increments, 1 time = 2n instructions

6.if(A[j] > A[j+1]) { // n-1 logical operations, 1 time = n-1 instructions

7.swap(A, j, j+1); // no swaps (arrangement is already sorted) = 0 instructions

8.changed=true; // no swaps (arrangement is already sorted) = 0 instructions

11.while(changed==true); // 1 logical operation (only 1 time, because the arrangement is already sorted) = 1 instruction

Thus, the sum of its instructions is equal to: 1 + 1 + 2n + (n-1) + 1. As we reduce this expression, we have that the algorithm performs a total of 3n+2 instructions. We say that T(n)=3n+2 is the time complexity formula of this algorithm in the “best case”. Another important aspect to note is that 3n+2 is a function of the 1st degree, so the Bubble Sort has linear complexity at “best case”.

Summing up:

  • In the “worst case”, the algorithm will have quadratic complexity: T(n)=5n2-n+1
  • In the best case, the algorithm will have linear complexity: T(n)=3n+2

Share this article

Share on whatsapp
WhatsApp
Share on facebook
Facebook
Share on twitter
Twitter
Share on linkedin
LinkedIn
Share on email
Email

Follow us
on our social media.