Big-O Notation

## Resources

1. Wikipedia
2. CompSci
3. Big-O Notation
4. Big-O For Sorting Algorithms
5. sorting.at
6. Visual Go

## Big-O Notation

Algorithm running times grow at different rates.

Big O doesn’t tell you the speed in seconds. Big O notation lets you compare the number of operations. It tells you how fast the algorithm grows and establishes a worst-case run time.

A simple search on an array takes O(n) times, whereas a binary search would take O(log n) given the nature of (log[2]n).

## Common Big-O Times

Here are five Big O run times that you’ll encounter a lot, sorted from fastest to slowest:

1. `O(log n)`, also known as log time. Example: Binary search.
2. `O(n)`, also known as linear time. Example: Simple search.
3. `O(n * log n)`. Example: A fast sorting algorithm, like quicksort.
4. `O(n2)`. Example: A slow sorting algorithm, like selection sort.
5. `O(n!)`. Example: A really slow algorithm, like the traveling salesperson.

## Big-O Time Complexity from Algorithms

AlgorithmBestAverageWorst
Selection SortΩ(n^2)θ(n^2)O(n^2)
Bubble SortΩ(n)θ(n^2)O(n^2)
Insertion SortΩ(n)θ(n^2)O(n^2)
Heap SortΩ(n log(n))θ(n log(n))O(n log(n))
Quick SortΩ(n log(n))θ(n log(n))O(n^2)
Merge SortΩ(n log(n))θ(n log(n))O(n log(n))
Bucket SortΩ(n+k)θ(n+k)O(n^2)

## Repository

https://github.com/okeeffed/developer-notes-nextjs/content/data-structures/understanding-big-o-notation