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.