Big-O
Before looking at the algorithms I should establish an idea of what Big-O is (to my understanding) and how we use it to analyze algorithms.
Big-O attempts to take away the little details of mathematical analysis of something like sorting or searching and sum it up in an abstract notation of 'O'. For example, if we have one algorithm that runs in (0.225n^2 + 0.32) seconds and another that runs in (0.47n^2 + 0.01n) seconds, we would suggest that both of these are the same in respect to O notation. Since both cases have a quadratic run time we say that they are both O(n^2). In analyzing algorithms, computer scientists take three things into account: the best case, the worst case, and the average case. This is done to possibly consider how the algorithm should be implemented or improved, or simply to analyze its speed. If the algorithm involves dividing a problem into tasks (e..g, binary search) computer scientists assume log n. Therefore, we express this thought as O(lg n). If the amount of steps of an algorthm increases in proportion to the size of n we express this as O(n). If the task takes the same amount of time regardless of the case (best/worst) it is referred to as O(1)--or constant.
Sorting Algorithms
In class we discussed four sorting algorithms: the selections sort, insertion sort, quick sort, and merge sort. I will focus on two of them to demonstrate the differences that can come about in Big-O analysis (and to keep this short). In analyzing sorting algorithms, scientists always consider how well the algorithm scales with an increase of size. Algorithm A can have incredible performance for a list size of 100 compared to algorithm B. However, say we increase the size to 1 million. A's performance dramatically decreases while B's is much better. Thus, algorithm's are tested at small and extraordinary scales to ensure we are not being deceived.
Selection sort works like this. For each list position in the list, loop through the entire list from that position to find the minimum item. If it smaller than the item at the current position, swap them. This algorithm is not so great. This sort is considered O(n^2). Recall, this means that the number of steps increases in proportion to the size of n, squared. With selection sort we can see that what makes it quadratic is the fact that it must do a full linear search of the list. We can conclude that there is a constant factor to this algorithm which insists it will take the same number of steps whatever the size. Therefore, best and worst case are the same.
The other sort, merge sort, is more interesting. It divides the list into n sub lists each of at least length 1 and sorts that sub list. It repeatedly merges those sub lists to create a sorted sublists. This continues until you have a single sorted list. The image to the right illustrates this concept well. This is an example of O(n lg n) complexity (best and worst case). This is a result of using the "divide and conquer" method in which every split (which takes O(n) time) is reducing the size of the array (thus the load of work--this is where lg n comes from).
