Data structure and Algorithms - BIG O Cheat Sheet
Big O Cheat Sheet: -Big Os- 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 nth items O(n log(n)) Log Linear - Usually for 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) -What can cause time in a function? - Operations (+, -, *, /) Comparisons (<, >, ==) Looping (for, while) Outside Function call (function ()) -Rule Book- 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 ...