Big O notation

Classification of algorithms running times given input X as X grows very large.

Smallest to Largest:

O(1) Constant

O(log n) Logarithmic

O(n^c) Fractional power, 0< c < 1

O(n) Linear

O(n log n) Linearithmic, O(n log n!)

O(n^2) Quadratic

O(n^x) Polynomial, x > 2

O(c^x) Exponential, c > 1

O(n!) Factorial

Logarithmic Running Time, an explanation

When computing the running time for some set of operations, how do you know whether something is log base 3 or 2 or 10. I will refer to log base x as log_x from here on out.

A set of operations will be said to take log_x steps if you're decreasing the work by a multiplicative factor. Take merge sort for example, we divide the list by 2, so that operation takes log_2 n (n being the size of the list). So if you're dividing the work by a constant amount each time, you end up with a logarithmic equation.

Also, all logs can be reduced to log_2. Why and how you might be wondering since you've probably noticed most running time of algorithms is always written in log_2.

That is because you can convert between any of the logs. They are all the same within a constant factor.

Equation:
log_b (n) = log_x (n) / log_x (b)

Example with converting from base 2 to 10:
log_2 (n) = log_10 (n) / log_10 (2)

log_2 (n) = log_10 (n) / constant

Real example of why a function's running time is logarithmic:

Take a list with 128 elements, apply merge sort to it. With merge sort, you keep dividing by 2:

128

64 64

32 32 32 32

16 16 16 16 16 16 16 16 16 16

..

2...2

At each step you process all n numbers, and there are 7 steps you have to do to reach the final answer, so that's where you get log_2 128 = 7

What the algorithm looks like if mapped on an x, y axis:

The logarithmic function measures the rate of growth. It is the inverse of the exponential function. As a result, it is a slow growth function (opposite of an exponential function).

An exponential function's graph is a U split down the middle with the origin at the bottom of the U starting at (0,0). We care only about the +x, + y axis. Since the logarithm function is the inverse, its graph is a U turned on its right side. Half of the U is on the +x, +y axis, the other on the +x, -y axis with the origin (0, 0). You can tell for very large input, growth will be slow.

Inverse relationship example:

log_2 128 = 7

2 ^7 = 128

Properties of Sorting Algorithms

Run time complexity:

Amount of steps/number of operations required to complete the algorithm.

Performance:

How fast can the algorithm run? This is a bit different then running time complexity because here you care about how long an operation takes. For example, if you need to look up something in a DB to complete your sorting, because let us say a list only has ids but you want it sorted according to names as well - looking up those names is expensive and takes time.

//how long it would take to carry out 10 operations of varying lengths:
10 operations of x (each x takes 10 ms) = 10 x 10 ms = 100 ms
10 operations of y (each y takes 100 ms) = 10 x 100 ms = 1000 ms

Another topic that falls under performance is cache locality. Whether you're frequently accessing similar items while you're processing a list is important, especially when your list is large and does not fit into memory. If you're constantly thrashing and moving things in and out of memory, you have bad cache locality. If you're working on a subset of a list, and then move on and work on the next subset without constantly thrashing (for example constantly traversing the entire list), you have good cache locality.

Good cache locality: quick sort
Bad cache locality: heap sort, merge sort (if not done in place)

Storage (in-place vs not):

Extra storage needed to hold things while sorting a list.

An algorithm is in-place if it does not need extra storage space while sorting the list (minus a few variables). For example, while the algorithm is sorting, it does not need to create a new list to put the sorted elements into, it can do the sorting and placing of elements in their proper place directly on the existing list.

Stable vs Non-Stable:

An algorithm is stable if it does not change the relative position of items that are equal.
So after sorting a list, the relative position of items that are equal stays the same guaranteed.

Sort the list below by GPA (high to low), input List below:
[(Anna, 4.0), (David, 4.0), (John, 2.0), (Kelly, 3.0)]

Stable should produce:
[(Anna, 4.0), (David, 4.0), (Kelly, 3.0), (John, 2.0)]

Relative position of Anna and David are maintained, Anna still comes before David.

It should not produce (while non-stable algorithms could produce this):
[(David, 4.0), (Anna, 4.0), (Kelly, 3.0), (John, 2.0)]

The sorting is correct, but the relative position of David and Anna is not the original.

You care to chose a stable sort if you care about the current order (because it has some property you want to preserve) of the list you're about to sort.

So like the example above, if I have a list sorted by alphabetical order, and now I want to sort by GPA while keeping the alphabetical order sorting. I'd want to chose a stable algorithm.

Why not just sort and just take into account the various properties? Who cares which algorithm you use? Because it might be expensive to look up the data to attain the exact sorting you want. Let us say you have a list with ids and GPAs only. You want that list sorted by alphabetical order of names, even though names aren't included. If the list is presorted alphabetically, you want to retain that sorting. Because if you do not, then you have to do a db look up (which is slow) to get the name to factor it into your sorting equation when doing the sort.

Merge Sort

Merge sort is a divide and conquer algorithm that works by dividing a list continuously and then merging/sorting the smaller lists.

Average and Worst case running time: O(n logn)
n, because you visit all the elements to merge them. log n, because you're constantly split the array in 2, so n/2

Note: It is faster than quick sort because it has a lower constant.

Most implementations of quick sort require O(n) space. That's why some people prefer heap sort which is also O(nlogn) running time, but requires only constant space (O(1)).

An interesting note: Java uses a modified version of merge sort for their sort() algorithm

Implementation of merge sort that you can run:

import java.util.List;
import java.util.ArrayList;

class MergeSort {

   List <Integer> list;
  
   MergeSort() {
       list = new ArrayList<Integer>(6);
       System.out.println("size before we put anything in it: "+list.size());
       list.add(new Integer(1));
       list.add(new Integer(5));
       list.add(new Integer(3));
       list.add(new Integer(4));
       list.add(new Integer(20));
       list.add(new Integer(0));
       list.add(new Integer(6));
       list.add(new Integer(10));
   }

   public static void main (String args[]) {
       MergeSort ms = new MergeSort();
       ms.sort();
   }

   void sort() {
       if (list != null) {
           List<Integer> result = mergesorthelp(list);
          
           for (Integer i: result) {
               System.out.println(i);
           }
       }
   }
  
   List<Integer> mergesorthelp(List<Integer> list){

       if(list.isEmpty() || list.size() == 1) {
           return list;
       }
      
       List<Integer> a, b, result;

       a = mergesorthelp(list.subList(0, (list.size()/2)));
       b = mergesorthelp(list.subList((list.size()/2), list.size()));
      
       result = merge(a, b);
      
       return result;
   }
  
   List<Integer> merge (List<Integer> a, List<Integer> b) { 
       List<Integer> newList = new ArrayList<Integer>();
       int indexA = 0;
       int indexB = 0;
       int sizeA = a.size();
       int sizeB = b.size();
      
       while (indexA < sizeA || indexB < sizeB) {
           if (indexA < sizeA && indexB < sizeB) {
               if (a.get(indexA) > b.get(indexB)) {
                   newList.add(b.get(indexB));
                   indexB++;
               }
               else {
                   newList.add(a.get(indexA));
                   indexA++;
               }
           }
           else if (indexA < sizeA) {
               newList.add(a.get(indexA));
               indexA++;
           }
           else if (indexB < sizeB) {
               newList.add(b.get(indexB));
               indexB++;
           }
       }//end while
      
       return  newList;
   }
}

Bubble Sort

With this algorithm, you go through the array checking if each value is bigger than the one after it and you propagate/"bubble" the bigger item up the array (towards the end) by swapping it with the item next to it. Going through the array/list once constitutes as one pass. You will make as many passes as needed until the array is sorted(no swapping has taken place on the last pass).
Best Case: O(n), everything already sorted. You take one pass to figure that out.
Worst case running time: O(n^2).
In place: Yes.

Code:

swap = false;

do {
swap = false;
for (i = 0; i < size -1; i ++) { //you want to stop at the one before last since you're comparing the next item

if (arr[i] > arr[i+1]) {
swap (arr[i], arr[i+1]);
swap = true;
}

} while(swap)


What you will realize is that with the first pass, you're placing the biggest element at the end of the array (fixed in its correct place). 2nd pass: 2nd biggest element, etc. So you don't really need to iterate through the whole array every time, but arr.size - the pass you are on (since the items will be fixed in place).

swap = false;
int index = arr.size;

do {
swap = false;
for (i = 0; i < index -1; i ++) { //you want to stop at the one before last since you're comparing the next item

if (arr[i] > arr[i+1]) {
swap (arr[i], arr[i+1]);
swap = true;
}

index--;

} while(swap)



You will realize that for every element that is not in its place(off by 1), you will need 1 full pass to fix it it + final pass to go through the array and make sure everything is good.
1 swap to get arr ordered = 2 passes
2 swaps to get arr ordered = 3 passes
n = n+1 passes

To keep it easy, we will define 1 pass to mean you've visited all the elements (n). In reality its more like n-i, with i being pass count because as you put items in place you don't need to traverse to that point in the array. So if you know an array is almost sorted, say 4 elements are out of place/4 swaps are needed for the array to be sorted, then Big O is O(5n). Might be better than some other algorithms.

So worst case, the element is very off (at the other end of the array), you will need n+1 passes to fix it, and each pass you're examining n items. Thus, O(n^2).