Analysis of Algorithms - Part II

Big-oh computation in programs:

A programmer can easily determine the order of a code (or calculate the big-oh order for a particular code). Let’s consider some examples:

1.) Constant time:

int n=5;
cout<<(n+5);

For such normal statements we consider them as being O(1) because they don’t depend on the input. A statement would depend on the input only if we are using some form a loop.

A question arises: “If we have hundred such normal statements what is the order?”

The order is still denoted as O(1), because it is still constant-time and doesn’t depend on the size of the input.

2.) Linear time:

for(int i=0; i<n; i++)
{
if (array[i] == required_value)
{
    cout<<endl<< “Required value present at position:”<<i;
    break;
}
}

This is a simple code snippet implementing the linear search algorithm. The loop would execute a maximum of ‘n’ times (worst case scenario). The number of iterations depends on the size of the input (i.e. on the value of ‘n’).

This code has an order: O(n).

3.) Combination of loops and normal statements:

When there are a few normal statements (constant time) and a loop which depends on ‘n’, then we consider the worst running time. Between O(1) and O(n), we choose O(n) as the order for that program.

int n=5;
cout<<(n+5);
for(int i=0; i<n; i++)
{
if (array[i] == required_value)
    {
    cout<<endl<< “Required value present at position:”<<i;
    break;
    }
}

Overall big-Oh notation for this code: O(n).

Remember: Big-oh notation represents the worst-case scenario.

Binary search seems to be more effective than linear searching; but we have a problem. For binary search to work the input should be in sorted order. It is a prerequisite. This brings us to the next problem; that of sorting data. There are many ways of sorting data and we’ll take a look at some of the commonly used sorting algorithms.

A very simple way to sort is to just keep comparing neighbouring two elements and then swap them in case the first element is larger than the second (for descending order it’ll be the reverse but we’ll assume that we want to sort a given set of elements in ascending order).

Let’s assume that we have 5 elements 5, 4, 3, 2 and 1. The idea is to arrange them in ascending order.

With this one round of sorting is complete. For the next round we repeat the same process but this time the element chosen will be 4.

After four rounds, the elements will be in sorted ascending order.

As can be seen from the figures, we’ll need a total of (n-1) main sorting rounds. And within each main round, we have (n-1) little rounds. If implemented in a program, we would need to use two loops to implement this algorithm.

You might have noticed from the above figures that the smaller values actually bubble their way to the top. This algorithm for sorting is called bubble sorting.

You might have also noticed that after each main sort round, we can reduce the number of little rounds by one. Just take a look at the earlier figures and you’ll get the idea.

If the input happens to be in sorted order (say after the second round), then we needn’t perform the other rounds. If it’s already sorted why should we continue with the algorithm? To implement this, we can use a variable which counts the number of swaps in each main round. If there are no swaps in a main round, then we can break out of the main sorting loop.

A few other sorting algorithms are selection sort, insertion sort and quick sort. Each one has its own advantages and disadvantages and exploring these algorithms is left as an exercise for the reader.