> 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/61b/asymptotics.md).

# Asymptotics

## Scaling

The **scaling** of an algorithm refers to its behavior in terms of speed and resource consumption as the number of things it has to process increases. 

We want our "interpretation" of how long an algorithm takes to be mathematical, as well as consider only the worst case.

## Notation

| Symbol        | Use                                                                                                                                                                                                                                              |
| ------------- | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ |
| $$\Theta(N)$$ | Denotes the *family of functions* that grow with the order specified in the notation. Mathematically, it means that given $$R(N) \in \Theta(f(N))$$ , there are two positive constants $$k\_1,k\_2$$ , where $$k\_1f(N)\leq R(N)\leq k\_2f(N)$$. |
| $$O(N)$$      | If you think of big theta as equals, you can think of big O as less than or equal. This just means that $$R(N) \in O(f(N))$$ , then $$R(N)\leq k\_2f(N)$$ for some positive integer $$k\_2$$. Usually represents the worst-case scenario.        |
| $$\Omega(N)$$ | Opposite of $$O(N)$$ and represents the best case scenario. Not really used too often.                                                                                                                                                           |

## Two Useful Things

| Runtime         | Summation                                            |
| --------------- | ---------------------------------------------------- |
| $$\Theta(N^2)$$ | Sum of first natural numbers `1 + 2 + 3 + 4 ... + N` |
| $$\Theta(N)$$   | Sum of first powers of 2 `1 + 2 + 4 + 8 ... + N`     |