_index.org

parametricity of learning algorithms

Last edited: September 9, 2025

Non-Parametric Learning Algorithm

The memory usage of the algorithm grow linearly as a function of the size of the dataset \(n\).

Parametric Learning Algorithm

There’s a fixed set of parameters \(\theta_{i}\) that you learn once, which you then use to make predictions. You don’t need to keep the dataset around.

Roughgarden 1

Last edited: September 9, 2025

sorting

Last edited: September 9, 2025

constituents

  • a list of elements of length \(n\)
  • all \(n\) elements are distinct

Speed is measured as a function of \(n\).

requirements

List becomes sorted

additional information

SU-CS161 SEP232025

Last edited: September 9, 2025

Divide and Conquer

Break problem into smaller sub-problems.

example: multiplication

Multiplying by powers of ten is easy, so we can break a multiplication into smaller groups.

For instance, we can break \(n\) digit integer into:

\begin{equation} [x_1, x_2, \dots, x_{\frac{n}{2}}] \times 10^{\frac{n}{2}} + [x_{\frac{n}{2}+1}, x_{\frac{n}{2}+2}, \dots] \end{equation}

Then we can multiply two large values by writing:

\begin{align} x \times y &= \qty(a \times 10^{\frac{n}{2}} + b ) \qty(c \times 10^{\frac{n}{2}} + d) \\ &= \qty(a \times c ) 10^{n} + \qty(a \times d + c \times b) 10^{\frac{n}{2}} + \qty( b \times d) \end{align}

SU-CS161 SEP252025

Last edited: September 9, 2025

Key Sequence

Notation

New Concepts

Important Results / Claims

quantifying success