Sorting Out the Big-O

Back in high school, list sorting was like:

>>> l = [6, 8, 3, 5, 1, 2, 4, 7]

>>> l.sort()

>>> l

[1, 2, 3, 4, 5, 6, 7, 8]

Those were good times.

Now I know that there are different ways to sort a list: bubble sort, insertion sort, selection sort, merge sort, quick sort, etc. Learning these types of sorts (whose code and descriptions can be found here) is useful for understanding the difference in efficiency one implementation of a working code can make over another.

The efficiency of a program is determined by how many steps it takes to solve a problem depending on the size of the problem. In the case of list sorting, the runtime would be determined by the length of the list. We count steps rather than speed to avoid including the factor of differences in CPU speed. Computer scientists like to look at the worst case runtime not because they're pessimistic but because knowing the most number of steps a program will take allows for an upper bound to be put on it.

The runtime of a program is denoted as some function of the problem size. This is useful for predicting how much longer a program will take to run as the problem size increases. For example, the function for the worst case runtime of bubble sort is n². This means that if the length of the list were to double, the runtime would be four times longer. Contrasting this with merge sort's nlogn runtime, it is evident bubble sort is not as efficient.

The worst case runtime of a program is denoted as O(function). For example, bubble sort has O(n²) and merge sort has O(nlogn). Bubble sort is jealous.

This is called Big-O notation. Because it's kind of a big deal.
...I'll see myself out now.

A Recursive Forest

When we first started learning about trees in CSC148, I thought they were just another tool to help get across the concept of  recursion. It didn't occur to me how useful this data structure was on its own until we encountered binary search trees.

Binary search trees are trees with the special characteristics of allowing every node only two children with the child on the left strictly smaller than its parent and the child on the right strictly greater than its parent. Having this specification allows us to search for a value in the tree very efficiently. When checking if a number is in a binary search tree we first check to see if it is the root. If not, we compare the value of the number to whether or not it is less than the value of the root. If that is the case, we know that if the number is in the tree, it must be located in the left subtree; if not, we know that we should do the remaining checks in the right subtree. This method always eliminates half of the tree or subtree it checks giving it a runtime of O(lg(n)).

Linear search, please exit stage left.

Codepanda vs. Recursion

Recursion and I met several years back. We did not get a very good first impression of each other and ultimately decided it would be best to go our separate ways. Time went by and our relationship dissolved into nothing. That is until we suddenly bumped into each other in CSC148 this semester. Talk about awkward....

The problem I had with recursion was that it could not be traced like for loops or while loops. When I first encountered it, recursion was explained in an extremely confusing way. Apparently a way that humans should not learn it. Throughout the past month I attempted to relearn recursion and I think I have gotten the basic idea of it.

Recursion is basically observed as a function calling itself. You can see how this ties in with the idea of looping. Programs that are recursively implemented can often be written with regular loops. However, the power of recursion lies in the efficiency it provides for the program. Code written to solve a problem recursively will run faster than code that solves the same problem with a loop.

There are two components to the basic recursive function: the confusing, self-calling function part and the base case.

The base case is what you want the function to do when the simplest, most basic argument is passed in. For example, if you want to determine the sum of the values in a nested list, the base case would be the function's behavior when a flat list is given. If you wanted the function to calculate a number's factorial, the base case would be evaluating 1! (exclamation mark = factorial symbol, still using my indoor slogging voice).

The recursive part is used when the function is called with a more complicated argument. The function essentially breaks down the problem into smaller parts until it reaches the simplest problem which is the base case that it knows how to evaluate. Then it retraces its steps and fills in what it knows in order to give an answer to the original argument inputted.

The basic structure of recursive code is:

def function(arg):
        if base case:
                evaluate to this
        else:
                evaluate something with call to function(with_some_arg)

Whether the base case/recursive part are under the if or under the else clause is arbitrary.

The base case is very important since it tells the function when to stop recursing. Without the base case, the function will endlessly run the recursive call until python runs out of memory and leaves.

Here is a great example of a recursive function and how it works -> great example