Intuition:

• \(O\): \(\leq\) (function in the symbol is
• \(\theta\): \(=\)
• \(\Omega\): \(\geq\) (function in the symbol is a lower bound)

Definition Intuition:

We say \(f\qty(n) = O\qty(g\qty(n))\) such that “when \(n\) gets big enough, \(f\qty(n)\) is bounded by at most a constant multiple of \(g\qty(n)\).

Definitions:

• \(f(n) = O(g(n)) \Leftrightarrow \exists c, n_{0} > 0: \forall n > n_0, f(n) \leq c (g(n))\)
• \(f(n) = \Omega(g(n)) \implies \exists n_{0}: \forall n > n_0, f(n) \geq c (g(n))\)
• \(f(n) = \theta(g(n)) \implies \exists n_{0}: \forall n > n_0, f(n) \geq 1 (g(n)), f(n) \leq c (g(n))\)

Little ones:

a cost function \(J\) tells us how good our training is. For instance, least-squares error

additional information

It’s hard to make globally optimal solution, so therefore we instead make local progress.

constituents

• parameters \(\theta\)
• step size \(\alpha\)
• cost function \(J\) (and its derivative \(J’\))

requirements

let \(\theta^{(0)} = 0\) (or a random point), and then:

\begin{equation} \theta^{(t+1)} = \theta^{(t)} - \alpha J’\qty (\theta^{(t)}) \end{equation}

“update the weight by taking a step in the opposite direction of the gradient by weight”. We stop, btw, when its “good enough” because the training data noise is so much that like a little bit non-convergent optimization its fine.

Lecture

• SU-MED103 SEP252025

insertion sort is an algorithm that solves the sorting problem.

constituents

a sequence of \(n\) numbers \(\{a_1, \dots a_{n}\}\), called keys

intuition

Say you have a sorted list; sticking a new element into the list doesn’t change the fact that the list is sorted.

requirements

Insertion sort provides an ordered sequence \(\{a_1’, \dots a_{n}’\}\) s.t. \(a_1’ \leq \dots \leq a_{n}’\)

void insertion_sort(int length, int *A) {
    for (int j=1; j<length; j++) {
        int key = A[j];

        // insert the key correctly into the
        // sorted sequence, when appropriate
        int i = j-1;

        while (i > 0 && A[i] > key) { // if things before had
                                      // larger key
            // move them
            A[i+1] = A[i]; // move it down
            // move our current value down
            i -= 1;
        }

        // put our new element into the correct palace
        A[i+1] = key;
    }
}

This is an \(O\qty(n^{2})\) algorithm.