Home

Understanding Big-O Notation

Big-O Notation

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)
Radix SortΩ(nk)θ(nk)O(nk)

Repository

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

Sections


Related