A general recurrence relation solution formula. It’s a generalization of the “tree” method in example 1.

intuition

Every Recursion Theorem problem has a struggle between most work sitting at the “bottom” of the tree (number of subproblems explode, \(a > b^{d}\)) vs most work sitting at the “top” of the tree (problem lower in the tree are smaller, \(a < b^{d}\)).

constituents

Consider:

• \(a\): number of subproblems
• \(b\): input size shrink
• \(d\) need to do \(n^{d}\) work to merge subproblems

Suppose \(a \geq 1, b> 1\), and \(d\) are constants. Suppose \(T\qty(n) = aT\qty(\frac{n}{b}) + O\qty(n^{d})\), we then have:

Calculating the runtime of a recursive scheme.

requirements

• A recursive function \(T\qty(n)\) in terms of \(T\qty(k), k< n\)
• A base case \(T\qty(1)\)

additional information

motivation

Consider merge sort. It’s running time is of shape:

\begin{equation} T\qty(n) = 2 T\qty(\frac{n}{2}) + O\qty(n) \end{equation}

Two submerges, plus the \(O\qty(n)\) merge operation. For the sake of argument clarity (not to mix Big-oh notation and just the recurrence relation), let’s write \(O\qty(n) := 11n\).

\begin{equation} T\qty(n) = 2 T\qty(\frac{n}{2}) + 11n \end{equation}

Key Sequence

Notation

New Concepts

• recurrence relation
• master theorem
• substitution method

Important Results / Claims

Questions

Interesting Factoids

See Linear Regression

example: house price prediction

1 dimension

We want to predict sales price from feet above ground.

\begin{equation} h(x) = \theta_{0} + \theta_{1} x \end{equation}

This makes: \(h : \mathbb{R} \to \mathbb{R}\). and the \(\theta = \qty(\theta_{0}, \theta_{1})\) are what we call parameters or weights.

d dimensions

\begin{equation} h(x) = \theta_{0} + \sum_{j=1}^{d}\theta_{j}x_{j} \end{equation}

but this is like clumsy, so if we come up with a special feature \(x_0 = 1\), we can just make it the linear model it is:

See Normal Equation

for small equations of Linear Regression, we can solve it using normal equation method.

Consider \(d\) dimensional feature and \(n\) samples of data. Remember, including the dummy feature, we have a matrix: \(X \in \mathbb{R}^{n \times \qty(d+1)}\) and a target \(Y \in \mathbb{R}^{n}\).

Notice:

\begin{equation} J\qty(\theta) = \frac{1}{2} \sum_{i=1}^{n} \qty(h_{\theta} \qty(x^{(i)}) - y^{(i)})^{2} \end{equation}

and \(h = X \theta\), we we can write:

\begin{equation} J(\theta) = \frac{1}{2} \qty(X \theta - y)^{T} \qty(X \theta - y) \end{equation}