Time Complexity Cheat Sheet

time-complexity.md

Top Down Recursive DP:

Non-memoized:

dp(n) => O((number of recursive calls) ^ (number of inputs))

• recursive calls is how many times backtrack(...) is called recursively

Fibonacci:

         f(4)
         / \ 
      f(3) f(2)
      / \    \   \
   f(2) f(1) f(1) f(0)
   / |     
f(1) f(0)

Depth of callstack is n, because there are n levels in the recursion tree. Max depth of JavaScript callstack depends on the browser.

Number of recursive calls is approximately 2^n

dp(n, m) => O((number of recursive calls) ^ (number of inputs))

Memoized:

dp(n) => O(n)

dp(n, m) => O(n * m), but can be more complicated like polynomial, etc.

Memoized dp can be represented as a directed acyclic graph (DAG).

Fibonacci memoized:

         f(4)
         /  
      f(3) 
      /     
   f(2)     
   / |     
f(1) f(0)

Prefix Tree (trie)

insert()

• Time: O(average length of words * number of words)
• Space: O(average length of words * number of words)

search(string) Time: O(average length of words * number of words)

Subsets

(returns unique results of every length)

Time: O (2^n)

Space: O (length of nums) for call stack

Permutations

Time: O(n!)

Space: O(n) call stack

Union Find

Without path-compression or rank: O(n^2)

With path-compression and rank: O(log n -> n)

Graphs

Adjacency List BFS

Time: O(nodes + connections) or: (V + E)

Space: O(nodes + connections)

2d Matrix BFS

Time: O(3^nodes)

Heaps

Insert

Time: O(log number of inserted items)

Space: O(number of inserted items)

Extract

Time: O(log number of inserted items)

Space: O(number of inserted items)