# 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](https://4258085521-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F9G7bk8jPRz85XaeJtlxH%2Fuploads%2Fgit-blob-d59da137de1682022596b9baf00e99cd5c95e64a%2Faymptotics-table.png?alt=media)

## 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](https://4258085521-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F9G7bk8jPRz85XaeJtlxH%2Fuploads%2Fgit-blob-81a9506e4b2cee4fa4eba32a58d1f17b300efe63%2Fdecision-tree.png?alt=media)

### Hasse Diagram

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

![Hasse Diagram Example](https://4258085521-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F9G7bk8jPRz85XaeJtlxH%2Fuploads%2Fgit-blob-f9a48203bb5bd8e9794818ac7b58f2f0bd54e56c%2Fhasse-diagram.png?alt=media)