Algorithm Analysis ( Big-O )

Algorithm analysis is how we determine how efficient a solution is. To sum it up, it is the worst case number of operations based on the size of the input.

Basic Search

If you have an array of unordered elements in an array. 
#define SIZE 5
    int arr[SIZE] = { 5, 3, 4, 2, 1 };
    int search_for = 1;
    int ops = 0;
    
    while ( ( ops < SIZE ) && ( search_for != arr[ops] ) )
    {
        ops++
    }
    cout << " it took " << ops <<
        " operations to find " << search_for << endl;
Since the are 5 elements and it takes 5 operations, this is Big-O of n, which is expressed as O(n). Keep in mind that we are looking for the worst case, so even if 1 was the first element in the array the Big-O would still be O(n). No matter how big the array is the worst case is n comparisions to find it, since it could be the last one in the list.

Bubble Sort

#define SIZE 5
    // bubble sort
    int arr[SIZE] = { 5, 4, 3, 2, 1 };
    for( int i = 0 ; i < ( SIZE - 1 ) ; i++ )
    {
        bool exhange = false;
        // each pass the highest remaining is in place
        for( int j = 0 ; j < ( SIZE - 1 - i ) ; j++ )
        {
            // compare adjacent
            if ( arr[j] > arr[j+1] )
            {
                swap( arr[j], arr[j+1] );
                exchange = true;
            }
        }
        if ( !exchange )
            break;
    }
So here is we look at the operations done, the passes through the search do ( 4 + 3 + 2 + 1 ) 10 comparisions. If we reduce the expression in terms of the size this is actually (n ( n-1 ) )/2. When it comes to analysis we don't get that picky since if n is big ( I mean really big ) the constants don't really impact the worst case very much. This sort would be considered to be O(n2).

Selction Sort

#define SIZE 5
    // selection sort
    int arr[SIZE] = { 5, 3, 1, 2, 4 };
    for( int i = 0 ; i < ( SIZE - 1 ) ; i++ )
    {
        int mark = i;
        // find the lowest, each pass start at the next
        for( int j = i+1 ; j < SIZE ; j++ )
        {
            if ( arr[j] < arr[mark] )
                mark = j;
        }
        if ( mark != i )
        {
            swap( arr[mark], arr[i] );
        }
    }
This sort has the same number of comparisons ( 4 + 3 + 2 + 1 ), which we know is O(n2) for comparisions. It does have an advantage on the swaps however, in the worst case it would do n - 1 swaps, again if we eliminate the constants, this would be be O(n) for swaps. Since we pick the dominate algebraic term, this sort would be considered to be O(n2).

Boundries

I mentioned earlier that we discard the constants, to reduce the analysis to significant math expressions. Here is a list of the functions that we typically express Big-O in.

polynomial boundries

non-polynomial boundries