Big O
Last updated
Last updated
O(1) Constant - no loops
O(log N) Logarithmic - usually searching algorithms have log n if they are sorted (Binary Search)
O(n) Linear - for loops, while loops through n items
O(n log(n)) Log Linear - usually sorting operations
O(n^2) Quadratic - every element in a collection needs to be compared to ever other element. Two nested loops
O(2^n) Exponential - recursive algorithms that solves a problem of size N
O(n!) Factorial - you are adding a loop for every element
Iterating through half a collection is still O(n)
Two separate collections: O(a * b)
1
Constant
statement, one line of code
log(n)
Logarithmic
Divide and conquer (binary search)
n
Linear
Loop
n*log(n)
Linearithmic
Effective sorting algorithms
n^2
Quadratic
Double loop
n^3
Cubic
Triple loop
2^n
Exponential
Complex full search
Operations (+,-, \*, /)
Comparisons (<, >, ===)
Looping (for, while)
Outside Function call (function())
Worst case
Best case
Worst case
Insertion Sort
O(1)
O(n)
O(n^2)
Selection Sort
O(1)
O(n^2)
O(n^2)
Bubble Sort
O(1)
O(n)
O(n^2)
Mergesort
O(n)
O(n log n)
O(n log n)
Quicksort
O(log n)
O(n log n)
O(n^2)
Heapsort
O(1)
O(n log n)
O(n log n)
Array
O(1)
O(n)
O(n)
O(n)
O(n)
Stack
O(n)
O(n)
O(1)
O(1)
O(n)
Queue
O(n)
O(n)
O(1)
O(1)
O(n)
Singly-Linked List
O(n)
O(n)
O(1)
O(1)
O(n)
Doubly-Linked List
O(n)
O(n)
O(1)
O(1)
O(n)
Hash Table
N/A
O(n)
O(n)
O(n)
O(n)
Rule 1: Always worst Case
Rule 2: Remove Constants
Rule 3:
Different inputs should have different variables: O(a + b).
A and B arrays nested would be: O(a * b)
+ for steps in order
* for nested steps
Rule 4: Drop Non-dominant terms
Variables
Data Structures
Function Call
Allocations