Runtimes, Big O Notation.

Simply put a programs runtime is how long it takes a given program to run.
Normally you would think of a computer running your programs near instantly, with little or no delay. This is due to the fact that the majority of programs written by beginners are simple in concept.

Runtimes become an issue when you move to more advanced programs, or begin to use more data in your program. As an example of this, assume you have a list of intergers. [1, 2, 3, 4, 5, 6]
In order to check if a certain number is in the list, a computer must check the first number, then if it is not the number you are looking for, then check the next number. It does this for every number in the list or until the number you are looking for is found.
In the worse case, it would take 6 checks to find the number you are looking for, or to determine the number is not in the list. If you had 10 items in the list, in the worse case you would need 10 checks. If you had 1000 items, you would need 1000 checks.
If you had n items, you would need n checks.

Big O notation is a way of indicateing the worse case scenario of runtimes.
This makes searching a list for one number be O(n) (Pronouced Big O of N).
O(n) is a linear runtime, meaning that if each item added has a constant increase to the number of steps needing to be preformed.

An example of a O(n^2) would be:

#Given n items
for i in n:
    for j in n:
        print(i, j)

This program has an O(n^2) because you must run the inner loop n times per each cycle of the outer loop. Since the outer loop also runs n times, you have n*n or n^2.

I mentioned last week that a Binary Search (using a binary search tree) has an O(lgn)
lgn is eqivilent to Log2(n). This is because in each case in the tree you are able to eliminate half of remaining tree with each check.

Binary Search Trees

As I've explained before, a binary tree is an Abstract data type (ADT) which has one root node, and (up to) two child nodes.

In a binary tree, the values or objects stored may not be in any particular order or form. This means that in order to find a specific object, you would have to traverse the entire tree.

Enter the binary search tree (BST).
A BST operates under the idea that the first value entered becomes the root node for the whole tree. If the second number entered is less than the root (first) node, then it becomes the left child. If it is greater it becomes the right child. This process is repeated for each time an object is added to the tree. It is important to note that a BST can not have duplicates of the same value.
 

For the tree above, the first item added is the 8. This becomes the root of the tree.
Next, a 3 is added. Since 3 is less than 8 it becomes the left child.
Next, a 1 is added. Since 1 is less than 8, and 1 is less than 3, it becomes the left child of 3.
Next, a 10 is added. Since 10 is greater than 8, 10 becomes the right child.
Next a 14 is added. Since 14 is greater than 8, and 14 is greater than 10, it becomes the right child of 10.
Next, 13 is added. Since 13 is greater than 8, and 13 is greater than 10, it must be to the right of both 8 and 10. However, since 13 is less than 14, 13 becomes the left child of 14.
If we keep going in this fashion, we can finish building the binary search tree.
It is important to keep in mind that the order that you add items to a BST changes the shape of the tree.

When you have a BST, it makes it fast to check whether a specific value is within the tree. For example, if we are looking the number 6, the we would take the following steps to find it.

Start at the root.
If the root is greater than 6, check the left child.
If the root is less than 6, check the right child.
Since  8 > 6, check the left child (Node 3).
Since 3 < 6, check the right child (Node 6).
Congratulations, you found 6.

By having a binary search tree, we are able to eliminate one tree at each check, drastically reducing the number of Nodes we have to check in total. This means when searching, the BST has a O(lg n). (More on this later)