One finds limits by pushing them.
- Herbert Simon
The discipline of Computer Science is more than simply programming. We also aim to ensure that our programs are quick and efficient. This is where the theoretical workers of Computer Science came in and determined a simple method to classify the speed of algorithms: Big-O.
Big-O allows us to classify algorithms according to how the algorithm's computation time grow based on the size of the input (n). The fastest possible growth rate of an algorithm is constant, (i.e. it does not grow at all) and is represented by O(1). While somewhat slower algorithms can take n^2 time, growing twice as fast as the input. The slowest algorithms can be O(2^n), O(n!), or O(n^n), taking exponentially longer every time the input size grow.
But what is the big deal about quick and efficient algorithms? "Taking exponentially longer" might not sound too exciting in words, but what if we put it into numbers?
| Input(n) | O(1) | O(log(n)) | O(n) | O(n^2) | O(2^n) | O(n!) |
| 2 | 1 | 1 | 2 | 4 | 4 | 2 |
| 4 | 1 | 2 | 4 | 16 | 16 | 24 |
| 8 | 1 | 3 | 8 | 64 | 256 | 40320 |
| 16 | 1 | 4 | 16 | 256 | 65536 | 20922789888000 |
| 32 | 1 | 5 | 32 | 1024 | 4294967296 | ??? |
| 64 | 1 | 6 | 64 | 4096 | 18446744073709551616 more than the age of the universe in seconds | ??? |
| 128 | 1 | 7 | 128 | 16384 | 10^38 | ??? |
| 256 | 1 | 8 | 256 | 65536 | 10^77 | ??? |
| 512 | 1 | 9 | 512 | 262144 | 10^154 There are only 10^80 atoms in the observable universe. | ??? |
As you can see, for a input size as small as 512 item, an algorithm with big-O time complexity of O(2^n) is highly impractical. If you are wondering why I didn't calculate for O(n!), it is because there are 1167 digits in 512 factorial.
We can easily see that it is important for us to write quick and efficient algorithms if we want to get any work done before the universe ends. But one might ask, why do we use big-O when we can simply time our code? The problem with that is timing our code does not always give us the information we need due to various factors. Big-O is used an upper bound measurement. That means that an algorithm that grows at O(n) grows at most linearly. However, Big-O is not intended to estimate exactly how fast an algorithm is, only how fast it grows. Timing our algorithm on a computer subjects it to factors such as hardware restrictions, background processes, and various other problems, and will not allow us to properly measure an algorithm's growth rate. The best way to ensure that our measurement is correct is by analyzing it line by line.
We have seen an example already where we can measure the Big-O Time complexity - sorting algorithms. Sorting is a process that you may say "is easier said than done". Coming up with an efficient sorting algorithm is not trivial, and there are countless algorithms out there with Big-O Time complexity ranging from O(n^2) to O(n log (n)). Some may even argue that there are algorithms that can sort in O(n). However, this year we are only looking at some of the more commonly known algorithms: Merge Sort, Quicksort, Selection Sort, Insertion Sort, and Bubble Sort.
Here are the algorithms:
############ Selection sort ############
def find_min(L, i):
"""Return the index of the smallest item in L[i:]."""
smallest = i
for j in range(i + 1, len(L)):
if L[j] < L[smallest]:
smallest = j
return smallest
def selection_sort(L):
"""Sort the items in L in non-decreasing order."""
i = 0
while i != len(L) - 1:
# Find the smallest remaining item and move it to index i.
smallest = find_min(L, i)
L[smallest], L[i] = L[i], L[smallest]
i += 1
############ Insertion sort 1 ############
def insert(L, i):
"""Move L[i] to where it belongs in L[:i]"""
v = L[i]
while i > 0 and L[i - 1] > v:
L[i] = L[i - 1]
i -= 1
L[i] = v
def insertion_sort_1(L):
"""Sort the items in L in non-decreasing order."""
i = 1
# Insert each item i where it belongs in L[0:i + 1]
while i != len(L):
insert(L, i)
i += 1
############ Bubblesort 1 ############
def bubblesort_1(L):
"""Sort the items in L in non-decreasing order."""
j = len(L) - 1
while j != 0:
# Swap every item that is out of order.
for i in range(j):
if L[i] > L[i + 1]:
L[i], L[i + 1] = L[i + 1], L[i]
j -= 1
############ Mergesort 1 ############
def _merge_1(left, right):
"""Merge sorted lists left and right into a new list and return that new
list."""
result = []
i ,j = 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:]
result += right[j:]
return result
def _mergesort_1(L):
"""Return a new list that is a sorted version of list L."""
if len(L) < 2:
return L[:]
else:
middle = len(L) // 2
left = _mergesort_1(L[:middle])
right = _mergesort_1(L[middle:])
return _merge_1(left, right)
def mergesort_1(L):
"""Sort list L in non-decreasing order."""
L[:] = _mergesort_1(L)
############ Quicksort 1 ############
def _partition_1(L):
"""Rearrange L so that items < L[0] are at the beginning and items >= L[0]
are at the end, and return the new index for L[0]."""
v = L[0]
i = 1
j = len(L) - 1
while i <= j:
if L[i] < v:
i += 1
else:
L[i], L[j] = L[j], L[i]
j -= 1
L[0], L[j] = L[j], L[0]
return j
def _quicksort_1(L):
"""Sort L by partitioning it around the first item, then recursing."""
if len(L) <= 1:
return L
else:
pivot = _partition_1(L)
left = L[:pivot]
right = L[pivot + 1:]
return _quicksort_1(left) + [L[pivot]] + _quicksort_1(right)
def quicksort_1(L):
"""Sort list L in non-decreasing order."""
L[:] = _quicksort_1(L)
As we can, Selection Sort, Insertion Sort, and Bubble Sort all require at least 2 nested loops. Since both loops involve n as a condition, this makes the Big-O time complexity of all these algorithms O(n^2). On the other hand, Merge Sort and Quick Sort uses a "divide and conqueror" strategy by splitting up the list into multiple sublists, and sorting the sublist. This means that instead of requiring O(n^2), it has O(n log (n)). This makes Merge Sort and Quick Sort much superior algorithms, and a quick test by timing our algorithm can confirm that.
bubblesort_1 1000 items in 0.748769 selection_sort 1000 items in 0.475687 insertion_sort_1 1000 items in 0.429609 mergesort_1 1000 items in 0.030901 quicksort_1 1000 items in 0.029133
However, we can observe that even though Selection Sort, Bubble Sort, and Insertion Sort are in O(n^2), they do not take the same amount of time to compute. The same goes for Merge Sort and Quicksort. Once again, this is because Big-O does not measure exactly how fast the algorithm performs. It simply gives an upper bound representing how the algorithm will grow.
Depending on the implementation of the algorithm, even the same algorithm can have different run time. We can push the limit of an algorithm by reducing the number of calls it needs to do, and using optimized versions of various functions (e.g. min(), max()) whenever possible. However, this will never be able to change it's time complexity. Think of it as changing the starting position, but not the slope. Even a very well implemented Bubble sort will eventually lose to a poorly implemented merge sort!
