Foundation of Algorithm Analysis

- Recurrence: $T(n) = 2T\left(\dfrac{n}{2}\right) + n$ - Branching factor: $a = 2$ (each node makes 2 recursive calls) - Subproblem shrink factor: $b = 2$ (size divided by 2) - Cost at a node of size $m$: $m$ (the "$+n$" term) - Base case: $T(1) = \Theta(1)...

For $T(n) = aT\left(\frac{n}{b}\right) + f(n)$ with $a \geq 1$, $b 1$: Compute the critical exponent $\logb a$ and compare $f(n)$ with $n^{\logb a}$: Case Condition Result ------------------------- 1 $f(n) = O(n^{\logb a - \epsilon})$, $\epsilon 0$ $T(n) = ...

A recurrence relation is an equation or inequality that describes a function in terms of its values on smaller inputs. To solve a recurrence relation means to obtain a function defined on the natural numbers that satisfies the recurrence. When we analyze re...

For $T(n) = aT(n/b) + f(n)$ with $a \geq 1$, $b 1$, compare $f(n)$ with $n^{\logb a}$: - Case 1: $f(n) = O(n^{\logb a - \epsilon})$ $\Rightarrow$ $T(n) = \Theta(n^{\logb a})$ - Case 2: $f(n) = \Theta(n^{\logb a})$ $\Rightarrow$ $T(n) = \Theta(n^{\logb a}\lo...

The recursion tree method is a technique for solving recurrence relations by expanding the recurrence into a tree. Each node represents the cost incurred at a subproblem, and the children of a node represent the recursive subproblems generated. The total co...

- Part a: $T(n) = 7T(n/2) + n^2$ - Part b: $T(n) = 4T(n/4) + kn$ (where $k$ is a positive constant) For a recurrence $T(n) = aT(n/b) + f(n)$ with $a \geq 1$, $b 1$, compare $f(n)$ with $n^{\logb a}$: Case Condition Result ------------------------- 1 $f(n) =...

--- Big Oh notation gives the asymptotic upper bound of a function. Definition: A function f(x) is said to be O(g(x)) if and only if there exist two positive constants c and x₀ such that: For all x = x₀ : f(x) <= c g(x) This means g(n) is the upper bound of...

Algorithm complexity is a measure of the amount of time and/or space (memory) required by an algorithm as a function of the input size n. - Time Complexity -- the number of basic operations performed as a function of input size n (using the RAM model, where...

Definition: The Random Access Machine (RAM) model is a model for counting the steps in an algorithm in order to analyze its time complexity. In this model: - Basic operations (+, -, , /) are counted as 1 step - Memory references (read/write) are counted as ...

--- An algorithm is a finite set of instructions where each instruction can be executed in finite time to perform computation by taking some value as input and to produce value(s) as output. The following are the elementary properties (characteristics) of a...

Definition: Aggregate analysis is a technique used in amortized analysis that determines the upper bound T(n) on the total cost of a sequence of n operations, then calculates the average (amortized) cost per operation as T(n)/n. Steps in Aggregate Analysis:...

--- When analyzing an algorithm, the running time often depends not just on the size of the input but also on the particular instance of the input. To capture this, we define three cases: --- - It gives the lower bound on the running time of the algorithm f...

An algorithm is a finite set of instructions where each instruction can be executed in finite time, taking input value(s) and producing output value(s). The iterative approach is used here to find the maximum element. --- Input: Array A of n elements (index...