Design techniques formulas

Applies only when any fraction of an item may be taken. Solved by sorting items on $v_i/w_i$ in descending order and filling greedily until capacity is used up; only the last item taken can be partial. Time $O(n\log n)$.

$p_i$ is the probability of symbol $i$. If frequencies are given, divide each by the total frequency. $l_i$ is its codeword length (the depth of its leaf). Huffman's construction minimises $L$ over all prefix-free codes for the given distribution. When weights tie, different trees are possible, but they all have the same minimum $L$.

a = number of subproblems, n/b = size of each subproblem, f(n) = cost of the divide and combine steps outside the recursive calls.

The same bound holds in the best, average and worst cases, because the split does not depend on the input order. Merging needs $O(n)$ extra space (standard merge sort is not in-place). Merge sort is stable.

The worst case happens when the pivot is always the smallest or largest element, giving (n−1, 0) splits. Example: an already sorted or reverse-sorted array with the first or last element as pivot. The best case is a perfectly balanced split. Any split in a fixed proportion (e.g. 1:9) still gives $O(n\log n)$. The average case (random pivot, or all input orders equally likely) is also $\Theta (n\log n)$. Partitioning needs no auxiliary array, but the recursion stack uses $O(\log n)$ space on average and $O(n)$ in the worst case. Quicksort is not stable.

Requires a sorted array (or a search space that is monotonic in the property being tested). The iterative version uses $O(1)$ extra space and the recursive one $O(\log n)$ stack. Inside $O(\cdot )$ the base of the logarithm does not matter; when an exact count is needed, use base 2.

This is the divide-and-conquer bound. Kadane's algorithm solves the same problem in $\Theta (n)$ with a single linear scan (a DP-style running "best sum ending here"). That is asymptotically better, and optimal, since every element must be read.

The answer is ${\max }_i\text{best\_end\_here}(i)$. It runs in $O(n)$ time with $O(1)$ extra space. With non-empty subarrays, an all-negative array returns its largest element.

Indices are 1-based here: $x_i$ is the i-th character of X and $y_j$ the j-th of Y. The table is $(m+1)\times (n+1)$, and time and space are both $\Theta (mn)$. If only the length is needed, not the subsequence itself, two rows are enough, giving $O(\min (m,n))$ space.

In the last case the three terms are delete $x_i$, insert $y_j$ and substitute. $D(i,0)=i$ means deleting all i characters of X's prefix; $D(0,j)=j$ means inserting all j characters. The table is $(m+1)\times (n+1)$, filled in $\Theta (mn)$ time. If only insertions and deletions are allowed, a match still copies $D(i-1,j-1)$, but a mismatch gives $1+\min (D(i-1,j),D(i,j-1))$. That distance equals $m+n-2\cdot \text{LCS}(X,Y)$.

$K(i,c)$ = best value using the first i items with capacity c. The table is $(n+1)\times (W+1)$, filled in $\Theta (nW)$ time. This is pseudo-polynomial: polynomial in the numeric value of W, but exponential in the number of bits needed to write W. The DP is therefore efficient for small integer W, while 0/1 knapsack in general is NP-hard. Space can be reduced to $O(W)$ with one array, if c runs from W down to $w_i$ for each item.

$S(i,t)$ is true if and only if some subset of the first i numbers sums exactly to t. Base cases: $S(0,0)=\text{true}$ and $S(0,t)=\text{false}$ for $t>0$. The table has $(n+1)\times (S+1)$ Boolean entries, filled in $O(nS)$ time, which is also pseudo-polynomial.

$m(i,j)$ is the minimum cost of multiplying $A_i{A}_{i+1}\cdots A_j$; a single matrix costs nothing. Fill by increasing chain length $l=j-i+1$ from 2 up to n. The answer is $m(1,n)$, the last cell filled. Time $\Theta (n^3)$ (indices i, j and split k), space $\Theta (n^2)$.