46 lines (32 loc) · 1.2 KB

Big O Cheat Sheet:

Big Os

O(1) Constant- no loops

O(n) Linear- for loops, while loops through n items

O(n^2) Quadratic- every element in a collection needs to be compared to ever other element. Two nested loops

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) or 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 in order
- for nested steps
Rule 4: Drop Non-dominant terms

https://www.bigocheatsheet.com/

What causes Space complexity?

Variables Data Structures Function Call Allocations