O(N), Big-O Notation for algorithms
Sorting Algorithm Performance
At it's most basic, we can see some algorithms are clearly just faster than others, for a bunch of input sizes we can compare best (Already sorted) and worst (sorted backwards) case times (in seconds) for two common-place algorithms (bubble-sort and merge-sort).
Here's the theory:
| | Best | Average | Worst | |---|---|---|---|---| | Bubble Sort | Ω(n log(n)) | Θ(n^2) | O(n^2) | | Merge Sort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) |
In case you aren't familiar with these algorithms, they are some of the most basic taught to first year computer science classes. Bubble sort will loop over the array in-place, swapping pairs of items one by one, until a complete iteration of the array does not perform any swaps. Merge sort on the other hand, uses divide and conquer to break the array into two pairs recurisvely and building a new array.
|Inputs||Bubble Sort (Best)||Bubble Sort (Worst)||Merge Sort (Best)||Merge Sort (Worst)|
Some things are easier to see in a graph, so have a look.
Searching Algorithm Performance
Here's a very common use case, we need to match two sets of related data. It could be displaying a list of students enrolled in each course from a list of enrolments.