> For the complete documentation index, see [llms.txt](https://notes.dizy.cc/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://notes.dizy.cc/fundamental-algorithms/introduction.md).

# Introduction

## Exponent rule

$$
\begin{gather\*} (a^b)^c = a^{bc} \end{gather\*}
$$

## Log rule

$$
\begin{gather\*} c^{\log\_a(n)} = n^{\log\_a(c)} \end{gather\*}
$$

## Asymptotics

| Name        | Notation        | Rough Meaning | Definition                                      | In-fix Notation |
| ----------- | --------------- | ------------- | ----------------------------------------------- | --------------- |
| big-Oh      | $$g=O(f)$$      | $$g \le f$$   | $$(\exists C > 0)\[C f \ge g \ge 0(e.v.)]$$     | $$g \preceq f$$ |
| big-Omega   | $$g=\Omega(f)$$ | $$g \ge f$$   | $$(\exists C > 0)\[C g \ge f \ge 0(e.v.)]$$     | $$g \succeq f$$ |
| Theta       | $$g=\Theta(f)$$ | $$g = f$$     | $$(\exists C > 1)\[C^2 f \ge C g \ge 0(e.v.)]$$ | $$g \asymp f$$  |
| small-oh    | $$g=o(f)$$      | $$g \ll f$$   | $$(\forall C > 0)\[C f \ge g \ge 0(e.v.)]$$     | $$g \ll f$$     |
| small-omega | $$g=\omega(f)$$ | $$g \gg f$$   | $$(\forall C > 0)\[C g \ge f \ge 0(e.v.)]$$     | $$g \gg f$$     |

![Asymptotics Notations](/files/WTTSOIxw3YjSQff2UwrN)

## Stirling's Approximation

Original:

$$\sqrt{2\pi n}({n \over e})^n e^{1\over{12n + 1}} < n! < \sqrt{2\pi n}({n \over e})^n e^{1\over{12n}}$$

$$log(n!) = n \log(n) - n + \Theta(\log(n))$$

Further simplification:

$$log(n!) = \Theta(n \log(n))$$

A possible transformation:

$$n! = \Theta(e^{n \log(n)})$$

## Comparison Tree

Example: Merge $$x\_1 < x\_2$$ and $$y\_1 < y\_2 < y\_3 < y\_4$$.

![Decision Tree Example](/files/LB3pwTXN9TtRao6YFZ5G)

### Hasse Diagram

The lower the smaller, circle(o) for x, cross(×) for y.

![Hasse Diagram Example](/files/stYYaGI2J7WXzmIPwU5z)