Efficiency of Algorithms

Algorithm is a recipe for solving a certain problem. It consists of a set of instructions which when followed step by step lead to the solution of the problem.

An algorithm needs to terminate in a finite number of precisely and unambiguously defined steps.

Popular ways of representing and algorithm are pseudocode and flow chart. The latter is more graphical.

Efficiency of an algorithm depends on its design and implementation. Since every algorithm uses computer resources to run, execution time and internal memory usage are important considerations to analyze an algorithm.

Below are some simple suggestions that can be useful in designing efficient algorithms :

Redundant computation :

Most of the inefficiencies of an algorithm are caused by redundant computation or unnecessary use of storage. This gets aggravated if expression calculations are embedded in a loop that gets executed multiple times. Expressions are be split to recalculate only the changing parts.

x = 0;
for(i = 1; i <= n; ++i){
  x = x + 0.05;
  y = (a * a * a + c) * x * x + b * b * x;
  printf("%f, %f", x, y);
}

Some of the recalculations can be avoided by precomputing constant parts of the expressions before the ‘for’ loop like -

x   = 0;
a3c = a * a * a + c;
b2  = b * b;
for(i = 1; i <= n; ++i) {
  x = x + 0.05;
  y = a3c * x * x + b2 * x;
  printf("%f, %f", x, y);
}

Referencing array element :

If care is not exercised, inefficiencies can also creep in due to array processing. Consider the below 2 ways of finding the maximum element in an array -

v1. 
pos = 0;
for (i = 1; i < arraySize; ++i) { 
  if (array[i] > array[pos]) {
     pos = i;
  }
}
max = array[pos];
v2. 
pos = 0;
max = array[0];
for (i = 1; i < arraySize; ++i) {
  if (array[i] > max) {
    max = array[i];
    pos = i;
  }
}

The v2 way would normally be preferred since the instruction (array[i] > max) is more efficient compared to (array[i] > array[pos])

‘array[pos]’ needs 2 memory references , first to locate start of ‘array’ and then to get the value of ‘pos’. Additionally we need to to traverse the array to get the ‘pos’ nth location in the array.

‘max’ needs just 1 memory reference to get the stored value.

Inefficiency due to late termination :

Suppose we have an alphabetically sorted list or dictionary of names. Consider we need to search for a specific name in the dictionary. An inefficient example of search implementation would be when search through the dictionary is continued even after a point when it is certain that the name cannot be found. Worse is when the loop continues even after it is found.

i = 0;
while(i < dictSize) {
  if (name != dict[i]) {
    i++;
  } else {
    printf("Found !!");
  }
}

More efficient example would be by doing early exit -

i = 0;
while( name <= dict[i] && i < dictSize) {
  if ( name == dict[i]) {
     printf("Found !!");
     break;
  }
  i++;
}

The quality of an algorithm can be judged by simple points like -

1. Simplicity of the solution, conciseness
2. Ease to modify
3. Independent of a particular computer, programming language or development environment.

Apart from these there has to be some measure to analyze and compare performance of algorithms that achieve the same solution. The popular mathematical notations used to indicate the computing time of algorithms are :

O notation (Big Oh)

Consider calculating first ‘n’ members of the fibonacci series (n≥ 2), along with the frequencies of each instruction.

a = 1;                            ---> frequency 1
b = 1;                            ---> frequency 1
printf("%d %d", a, b);            ---> frequency 1
for (i = 1; i <= (n - 2); ++i) {  ---> frequency n-1
  c = a + b;                      ---> frequency n-2
  printf("%d", c);                ---> frequency n-2
  a = b;                          ---> frequency n-2
  b = c;                          ---> frequency n-2
}

So, total frequency f(n) = 5n — 6

This can be amortized to O(n) . Since the degree of polynomial is ‘n’ it is also called linear time complexity. It is machine independent and grows linearly or in direct proportion to number fibonacci numbers ‘n’ to be calculated.

An algorithm which is even independent of the data set, is said to run in constant time and in denoted by O(1). For example , adding two numbers .

Simple article to understand different values of Big O https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation

Ω notation (Big Omega)

O - notation is used to represent the upper bound (worst case) run time of an algorithm whereas Ω is used to represent the lower bound or the best case scenario.

For the n-fibonacci numbers example, if n = 2, our function runs in a constant time which is the best case represented as f(n) = Ω(1)

ϴ notation (Big Theta)

When upper bound and lower bound of an algorithm are equal i.e both best case and worst case scenarios take the same amount of time within a constant factor, the complexity of that algorithm is represented by ϴ notation.

For example -

max = array[0];
for (i = 1; i < n; ++i){
  if(array[i] > max) {
     max = array[i];
  }
}

Computing time for above algorithm is both O(n) and Ω(n) since the ‘for’ loop will always execute (n-1) number of times. So we say that its time complexity is ϴ(n).

Above was a brief overview of what I feel might make your code work faster and an introduction to the concept of algorithmic time complexity. Please feel free to comment.