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)$