Week 11
Sorting and Efficiency 
I leaned sorting and efficiency in the class. We had to measure algorithm performance, which means that we leaned how to measure the running time. If input gets bigger, programs take more time to run it. We focused on size of the input and it is called n.
There are many types of input:
constant: c, logarithmic: c log n, linear: cn, cubic: cn^3, exponential: c2^n,,,

There are many types of sorting and some of them have different running time.

quick sort: O(n^2)
Quick sort chooses a pivot element in a list. It moves everything smaller than the pivot to one list (left sublist) and everything larger than the pivot to another list (right sublist). Then, quicksort the left sublists and right sublists. Then sorted list is made of left subtree, pivot, and right subtree. n steps are required to choose a pivot and n steps are required to compare each item in a list with the pivot.

merge sort: O(n log n)
Merge sort divides the list in half and mergesort the two divided list. Then merge the two sorted sorted halves in linear time. Merge sort divides a list log n steps and compare the each item in a list n times.