## 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) |
---|---|---|---|---|

2500 | 0.001 | 1.735 | 0.033 | 0.037 |

5000 | 0.001 | 6.845 | 0.089 | 0.088 |

7500 | 0.001 | 15.774 | 0.120 | 0.104 |

10000 | 0.002 | 29.932 | 0.137 | 0.126 |

12500 | 0.002 | 43.882 | 0.193 | 0.175 |

15000 | 0.002 | 63.401 | 0.211 | 0.202 |

17500 | 0.002 | 86.674 | 0.255 | 0.229 |

20000 | 0.003 | 113.058 | 0.297 | 0.278 |

22500 | 0.004 | 153.131 | 0.315 | 0.308 |

25000 | 0.005 | 176.978 | 0.351 | 0.437 |

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.

## Comments !