Tricky Time Complexity

list

List is like array so operation at beginning of the list is costly.

append: $O(1)$
insert(0, item): $O(n)$
pop: $O(1)$
pop(0): $O(n)$

deque

Because deque at its core is a double-linked list so it's more efficient than list

appendleft: $O(1)$
append: $O(1)$
pop: $O(1)$
popleft: $O(1)$
in: $O(n)$ — since it's a linked list

Heap Theory

findMin(): $O(1)$
- In python we just query heap[0]
pop(): $O(logn)$
- When calling pop() we need to start building the heap again to determine the lowest
insert(): $O(logn)$

set

in: $O(1)$
x.union(y): $O(x + y)$
x.intersect(y): $O(min(x, y))$

Sorted Set

in: $O(logn)$
add: $O(logn)$
remove: $O(logn)$

BFS

$O(V + E)$ with
- $V$ number of vertices — which is the same as the number of nodes.
  - So given an $m \times n$ array, $V$ would be $m \times n$
- $E$ number of edges — which is the connection between a node
  - For example a 3x2 array would have 7 $E$.
  - We can use the following formula: $$E = m \times (n-1) + n \times (m-1)$$
    - Which in this case $E = 3 \times 1 + 2 \times 2 = 7$

DFS recursion

Depends on how we call the recursion in the for dr,dc loop.
- If there is 4 and the total node we travel is m x n then it would be $O(4^{(m \times n)})$
- If there is 2 direction and the total node we travel is m + n then it would be $O(2^{(m + n)})$

Trie

Add w words of size l: $O(w * l)$
Search for word of size l: $O(l)$
Prefix $O(prefix)$

Skip List

Search: $O(logn)$
Insert: $O(logn)$
Delete: $O(logn)$

Permutation

Time compexity: $O(n \times n!)$ since the tree expands out from n items at the root and then n-1, n-2, n-3,... and at each pivot (start index) we have $n!$ ways of choosing

Combination Sum

Time complexity: $O(2^{target})$ since at each number we can either take or not (2 choices), and then we can choose duplication so sum up to a target

Subset

Time complexity: $O(n \times 2^{n})$ for $n$ number we will have $2^n$ subsets. And we perform the basket.copy() which will be $O(n)$