---
# System prepended metadata

title: Complexity Analysis

---

## VS Code Setup
- [Pytest](https://pytest.org/) Installation and Usage
- Tools
    - [Oh my zsh](https://ohmyz.sh/)
    - common Linux commands
    - VS Code plugins like Linter, code formatter, etc
## Curated Coding Problem List

See [Coding Review and Coding Interview](https://hackmd.io/dRptD9fmR0WERWwTZHwivQ) lecture outline.

## Idiomatic Python
- [Python Cheatsheet](https://github.com/ehmatthes/pcc/releases/download/v1.0.0/beginners_python_cheat_sheet_pcc_lists.pdf)
- [Google Python Style Guide](https://google.github.io/styleguide/pyguide.html)

## Linear Data Structure

### Array
![](https://i.imgur.com/GP2RRe9.png)

- Array Manipulation
    - [56. Merge Intervals](https://leetcode.com/problems/merge-intervals/)  
    - [121. Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock)
		
### Stack
![](https://i.imgur.com/hRWePvk.png)

[20.  Valid Parentheses](https://leetcode.com/problems/valid-parentheses/)  
[394.  Decode String](https://leetcode.com/problems/decode-string/)  
[739.  Daily Temperatures](https://leetcode.com/problems/daily-temperatures/)

### Queue
![](https://i.imgur.com/CepkCqr.png)

[225.  Implement Stack using Queues](https://leetcode.com/problems/implement-stack-using-queues/)  
[232.  Implement Queue using Stacks](https://leetcode.com/problems/implement-queue-using-stacks/)

### Linked List
![](https://i.imgur.com/mRH6xE6.png)

[206.  Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/)
[237.  Delete Node in a Linked List](https://leetcode.com/problems/delete-node-in-a-linked-list/)  
[83. Remove Duplicates from Sorted List](https://leetcode.com/problems/remove-duplicates-from-sorted-list/)  
### String
[344.  Reverse String](https://leetcode.com/problems/reverse-string/)  
[242.  Valid Anagram](https://leetcode.com/problems/valid-anagram/)  
Python String methods & complexity analysis

# Complexity Analysis
### Big O Notation
- Theoretical Analysis
- Practical Analysis
### Elementary Operations
- Insert
- Delete
- Search

|                      |  Insert  |   Delete   |  Search  | Space Usage  |
|----------------------|----------|------------|----------|--------------|
| Unsorted array       | O(1)     | O(1)       | O(n)     | O(n)         |
| Value-indexed array  | O(1)     | O(1)       | O(1)     | O(n)         |
| Sorted array         | O(n)     | O(n)       | O(log n) | O(n)         |
| Unsorted linked list | O(1)*    | O(n)*      | O(n)     | O(n)         |
| Sorted linked list   | O(n)*    | O(n)*      | O(n)     | O(n)         |
| Balanced binary tree | O(log n) | O(log n)   | O(log n) | O(n)         |
| Heap                 | O(log n) | O(log n)** | O(n)     | O(n)         |
| Hash table           | O(1)     | O(1)       | O(1)     | O(n)         |

 \* The cost to add or delete an element into a known location in the list 
   (i.e. if you have an iterator to the location) is O(1). If you don't 
   know the location, then you need to traverse the list to the location
   of deletion/insertion, which takes O(n) time. 

** The deletion cost is O(log n) for the minimum or maximum, O(n) for an
   arbitrary element.
   
# Non-linear Data Structure
![](https://i.imgur.com/fysVGpN.png)

### Hashtable/Hashmap

#### Hash Function
A function that maps a key to a hash value. For example, h(k) = k % m
#### Resolve Hash Collision
if m = 20,  

1 → 1 % 20 → 1  
5 → 5 % 20 → 5  
23 → 23 % 20 → 3  
63 → 63 % 20 → 3  

- Chaining
![](https://i.imgur.com/VTQep20.png)

- Open Addressing
![](https://i.imgur.com/F2ziBZh.png)

[Reference](https://en.wikipedia.org/wiki/Hash_table#Separate_chaining)
#### Efficient Lookup

### Tree
Tree is a subset of graph
- Tree Traversal 
	- DFS (Pre/In/Postorder traversal)
	- BFS (Level order traversal)  
	[104.  Maximum Depth of Binary Tree](https://leetcode.com/problems/maximum-depth-of-binary-tree/)  
	[404.  Sum of Left Leaves](https://leetcode.com/problems/sum-of-left-leaves/)  
	[513.  Find Bottom Left Tree Value](https://leetcode.com/problems/find-bottom-left-tree-value/)
- Binary Search Tree
![](https://i.imgur.com/jvswIyq.png)

	- [230.  Kth Smallest Element in a BST](https://leetcode.com/problems/kth-smallest-element-in-a-bst/)
	- [98.  Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree/)
	- [96.  Unique Binary Search Trees](https://leetcode.com/problems/unique-binary-search-trees/)
- Heap
![](https://i.imgur.com/0FOfMWV.png)

    - [215.  Kth Largest Element in an Array](https://leetcode.com/problems/kth-largest-element-in-an-array/)  
    - [23.  Merge k Sorted Lists/](https://leetcode.com/problems/merge-k-sorted-lists/)  
    - [973.  K Closest Points to Origin](https://leetcode.com/problems/k-closest-points-to-origin/)

- Trie(Prefix Tree)
![](https://i.imgur.com/40PN89U.png)

    - [211. Design Add and Search Words Data Structure
](https://leetcode.com/problems/design-add-and-search-words-data-structure/)

### Graph
![](https://i.imgur.com/YGQbUvI.png)

- Graph Traversal & Search
    - DFS
    - BFS
    
[133. Clone Graph](https://leetcode.com/problems/clone-graph/)  
[785. Is Graph Bipartite?](https://leetcode.com/problems/is-graph-bipartite/)  

[Reference](https://towardsdatascience.com/8-common-data-structures-every-programmer-must-know-171acf6a1a42)
## Algorithms

### Recursion


### Dynamic Programming
- Overlapping Subproblems
- Optimal Substructure

**Fibonacci Problem** 
- Plain Recursion
- Memoized Recursion
- Dynamic Programming

[Reference](https://medium.com/swlh/understanding-recursion-memoization-and-dynamic-programming-3-sides-of-the-same-coin-8c1f57ee5604)

### Sorting

- Basic Sorting
- Advanced Sorting
  - Heap Sort
  - Quick Sort
  - Merge Sort

