W2232 BigO Notation
Prerequisites[edit]
Background[edit]
 Watch Introduction to Big O Notation and Time Complexity (CS Dojo)
 Watch Getting Sorted & Big O Notation (Computerphile)
 Read A beginner's guide to Big O notation (Rob Bell)
 Watch Why My Teenage Code Was Terrible: Sorting Algorithms and Big O Notation (Tom Scott)
BigO Notation[edit]
BigO Notation is used to describe the performance of an algorithm and establishes a worstcase run time. It calculates the number of operations performed and the memory required for an algorithm to conclude. Different formulas can be used to calculate the operations performed and memory requirements for each sorting algorithm. BigO Notation is unable to tell you how long an algorithm will run because too many factors can influence the time an algorithm takes to run.
Common Formulas[edit]
O(log n)  Binary Search
O(n)  Linear Search
O(n * log n)  Quicksort
O(n^{2})  Bubble Sort/Insertion Sort/Selection Sort
Growth Rate  Name  Description 

O(1)  Constant  Statement 
O(log(n))  Logarithmic  Divide in half / Binary search 
O(n)  Linear  Loop 
O(n * log(n))  Linearithmic  Effective sorting algorithm 
O(n^^{2})  Quadratic  Nested loop 
O(n^^{3})  Cubic  Triplenested loop 
O(x^{n})  Example  Exhaustive search 
BigO Notation can also be calculated by hand. You can go through each line of code and determine if it will be "1", "log(n)", n, etc. You can then add up all the growth rates, and as one example, it can be expressed as O ( 1 + 3n) where the "1" represents one line of O(1), and the "3n" represents 3 lines of O(n).
Coming Soon  

Exercises[edit]
Write an essay (minimum 500 words) which:
 Defines BigO
 Compares and contrasts BigO for:
 BubbleSort
 Selection Sort
 Insertion Sort
 Merge Sort
 Based upon the above, which sort is most timeefficient for the average case?
Complete your essay in your Journal directory and push to GitHub.
References[edit]
BigO Notation for Beginners (AdrianMejia)
BigO Notation (Wikipedia)