Week 10 - Sorting Big-O

Ah. Big O.  The nightmare from CSC165 returns. What a familiar concept.  At least we're not doing proofs.

Anywho the Big O of an algorithm is defined as the upper bound on the runtime of an algorithm for the worst case scenario.  There's a lot of different Big O's out there but some of the most common ones are (in increasing horrible-ness)  constant, logarithmic, linear, quadratic, cubic, and exponential (ouch).  These factors are in terms of the size of the structure being processed by the algorithm (most commonly used at our level, I think, are lists)

We rarely (I think) get constant runtime.  Operations like assignment statements and prints have constant runtime, but they aren't really algorithms.  The simplest constant runtime algorithm I can think of is pop() for a list.  No matter the length of the list, the algorithm always goes to list[-1] and performs the same operation on it.  However, if we were to try to 'pop' the first item of the list, the runtime would be cn (where c is an arbitrary constant and n is the length of the list).  Since after deleting the first item, we would have to move every following item down an index number (ouch).

Lets look at binary search trees.  What's the big O on searching through the tree?

Since we know that each node has a left child which is less than the root and a right child that is more than the root, each time we pass a root we check if the item we're searching for is less than or greater than the root (or equal).  If it is less than or greater than, we automatically eliminate half of the items on our 'checking list'.  Hence, after each iteration, we divide the number of checks and hence the runtime, by half.  This is a O(logn) (note that this log is base 2).

Also, recall from CSC165 that since big O is an upper bound, O(logn) is in O(n) which is O(n^2) and so on. (yay subsets).

In CSC108 we learned three types of search algorithms - bubble search, selection search, and insertion sort.  All of which have pretty terrible efficiency.  Even Obama thinks so.

So far in this course, we've covered two new search algorithms: Quick sort and merge sort.

There are three basic steps of Quick sort:

1. Choose a pivot - this is the fastest step; a random index is usually used
2. Partition the list into two parts: less than the pivot and greater than the pivot
3. Repeat step 1 and 2 with recursion  until the list is sorted

As we did in CSC108, I feel like I should include a video of folkdance to demonstrate quicksort...so enjoy?

How do we evaluate quick sort's performance?:

• How many times do we choose the pivot?
• How many steps each time we choose a pivot?

Quick sort has a performance of nlogn - on average, we carry out the pivoting operations which splits the list in half (runtime of logn) and at each pivot split we do n work.  However in the worst case, the runtime could be n^2.

What about merge sort?

...Well...since we ran out of time in lecture and Danny's implementation didn't work...I think I'll leave that for next week.