Recall that Euler’s Equation exists:

\begin{equation} f(x) = e^{i k \omega x} = \cos (k\omega x) + i \sin(k\omega x) \end{equation}

and, for \(\omega = \frac{2\pi}{L}\), this is still \(L\) periodic!

Next up, we make an important note:

\begin{equation} e^{ik\omega x}, e^{-i k \omega x} \end{equation}

is linearly independent over \(x\).

inner product over complex-valued functions

recall all of the inner product properties. Now, for functions periodic over \([0,L]\) (recall we have double this if the function is period over \([-L, L]\):

A complex number is a type of number. They are usually written as \(a+bi\).

Formally—

\begin{equation} \mathbb{C} = \left\{a+bi\ \middle |\ a,b \in \mathbb{R} \right\} \end{equation}

This set generates solutions to every single polynomial with unique solutions. Its plane looks like \(\mathbb{R}^{2}\).

constituents

an order pair of two elements \((a,b)\) where \(a,b\in \mathbb{R}\).

properties of complex arithmetic

there are 6. For all statements below, we assume \(\alpha = a+bi\) and \(\beta=c+di\), \(\lambda = e+fi\), where \(a,b,c,d,e,f \in \mathbb{R}\) and therefore \(\alpha, \beta,\lambda \in \mathbb{C}\).

\begin{equation} \begin{cases} x_1’ = 5x_1 - 5x_2 \\ x_2’ = 2x_1 -x_2 \end{cases} \end{equation}

This gives rise to:

\begin{equation} A = \mqty(5 & -5 \\ 2 &-1) \end{equation}

Solving the characteristic polynomial gives:

\begin{equation} (5-\lambda)(-1-\lambda) + 10 = \lambda^{2} - 4\lambda +5 \end{equation}

Therefore, our solutions are imaginary!

\begin{equation} \lambda_{1}, \lambda_{2} = 2 \pm i \end{equation}

Aside: we only need to deal with one

Notably, anything that satisfies the original polynomial, its conjugates also satisfies:

complexity theory is a theory in algorithms to analyze time classes.

older Notes

We know that \(O(n\ log\ n)\) is between \(O(n)\) and \(O(n^2)\) — so we can roughly call it “polynomial time.”

Since the optimal comparison cannot be faster than polynomial time, we say that comparison-based sorting is a polynomial-time algorithm.

From this information, we can come up with two main time classes: \(P\) for solutions with known polynomial time, \(NP\) for non-deterministic polynomial time.