Recurrences and analysis tools

Словарь

English	Значение
algorithm design and analysis	Constructing algorithms and studying their correctness and resource costs.
recurrence/rɪˈkʌrəns/	An equation expressing a quantity, such as running time, using values for smaller inputs.
recursion tree	A diagram of recursive calls used to add work across levels of a recurrence.

English

The tree is the analysis

Algorithm design and analysis prices a design before writing it. A recurrence states a recursive algorithm's cost in terms of smaller inputs: $T(n) = 2T(n/2) + \Theta(n)$. The recursion tree draws it: level $i$ has $2^i$ nodes of $n/2^i$, every level costs $\Theta(n)$, the depth is $\log_2 n$ — so $T(n) = \Theta(n \log n)$.

{exercise:uni-cs1001-tree}

Практика

For T(n) = 2T(n/2) + n, one tree level costs —

Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня

English

For $T(n) = aT(n/b) + f(n)$, compare $f(n)$ with $n^{\log_b a}$ (the leaf total). Leaves dominate: $\Theta(n^{\log_b a})$. Balanced: $\Theta(f(n)\log n)$. Root dominates: $\Theta(f(n))$.
Course cases: $2T(n/2) + n \to n\log n$; $T(n/2) + 1 \to \log n$; $4T(n/2) + n \to n^2$ (leaves $n^{\log_2 4}$ dominate).

{exercise:uni-cs1001-master}

Практика

T(n) = 4T(n/2) + n solves to —

Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня

English

Guess $T(n) \le c\,n\log n$ for $2T(n/2) + n$: substitute and the induction closes whenever $c \ge 1$ — the guess becomes a proof.
Then measure: merge sort on the fixed 64-element course array makes $310$ comparisons, under the worst-case ceiling $n\log_2 n - n + 1 = 321$. Theory bounds, measurement confirms.

{exercise:uni-cs1001-substitute}

Практика

Merge sort on the 64-element course array makes — comparisons

Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня