What is the time complexity of solving Traveling Salesperson Problem (TSP) using Held-Karp Dynamic Programming algorithm?
Held-Karp DP table has O(n * $2^n)$ states, and computing each state takes O(n) transitions, giving total time O($n^2 * 2^n)$.
What is the space complexity of Held-Karp algorithm for TSP on n vertices?
The table stores C(S, v) where S is a subset of vertices and v in S. Number of states = O(n * $2^n)$.
What is the time complexity of computing the Optimal Binary Search Tree (OBST) cost for n keys using Dynamic Programming?
The standard DP table for OBST has size O($n^2)$, and finding the optimal root for each subproblem takes O(n) time, yielding O($n^3)$. (Knuth's optimization reduces it to O($n^2))$.
What is the main structural difference between MEMOIZATION and TABULATION in Dynamic Programming?
Memoization starts from the main problem and recursively solves required subproblems on demand. Tabulation iteratively fills the subproblem table starting from base cases.
When is MEMOIZATION preferable over TABULATION?
Top-down Memoization evaluates only the subproblems reachable from the root state, skipping unreachable subproblems. Tabulation systematically fills all table entries.