> For the complete documentation index, see [llms.txt](https://veriny.gitbook.io/berkeley/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://veriny.gitbook.io/berkeley/170/basics.md).

# Basics

## Asymptotic Notation

Suppose we have two functions $$f$$ and $$g$$which map positive integers to positive integers. 

| Name           | Notation | Definition            |
| -------------- | -------- | --------------------- |
| "Big-O"        |          | Less than or equal to |
| "Little-O"     |          | Less than             |
| "Big-Omega"    |          |                       |
| "Little-Omega" |          |                       |
| Theta          |          |                       |

## Master Theorem

A general formula to solve recurrence relation.\`Suppose we have a recurrence relation that resembles the following.

$$
T(n) = aT\left(\frac{n}{b}\right) + cn^d
$$

Then, we have $$\Theta(n^d)$$ if $$a < b^d$$, $$\theta(n^d\log(n))$$ if $$a = b^d$$, and $$\Theta(n^{\log\_ba})$$ for the final case.