What is Big O Notation
shows how efficient an algorithm is in the worst-case scenario relative to its input size
Omicron
Time Complexity
How much time does it take to run completely?
Space Complexity
How much extra space does it require in the process?
Ω
Omega
Best case scenario
Loop through [1, 2, 3, 4, 5, 6, 7] looking for 1
θ
Theta
Average case
Loop through [1, 2, 3, 4, 5, 6, 7] looking for 4
O
Omicron
Worst case
Loop through [1, 2, 3, 4, 5, 6, 7] looking for 7
Contiguous vs Noncontigous
Types of memory allocation
- Contiguous -single contiguous section/part of memory is allocated
- Noncontiguous - memory is allocated to different locations
Stack
Data Structure
- You can only get to the last item (most recently added) that you pushed onto the stack
- Example - back button in Web Browser will pop off the most recently visited site
Queue
Data Structure
- Typically FIFO
- Add on one end, remove on other end
Binary Tree
Data Structure
- nodes can have this.left and this.right values
- Full - every node either points to two nodes or zero nodes
- Perfect - Any level in the tree that has any nodes is completely filled across
- Complete -as long as left side is filled with no gaps
- Although Binary Tree will only have each node point to two nodes, other trees could have nodes that point to multiple nodes
Binary Search Tree
for any node:
* any nodes below and right will be greater than
* any nodes below and left will be less than
Big O of for loop
O(n)
Linear Time
Big O of arr.push() or arr.pop()
O(1)
Constant time
Big O of sorting algorithm
usually O(nlog n)
For JS array sort, depends on (browser) implementation
