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}

AISafety2025 Bansal: Safety Constrained Sets

Detect tokens (latents?) which trigger potential paths into unsafe behavior, and then preempt them early by steering.