> For the complete documentation index, see [llms.txt](https://isubasinghe.gitbook.io/isithas-wiki/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://isubasinghe.gitbook.io/isithas-wiki/computer_science/data_structures.md).

# data\_structures

## Basic idea

Concrete representations of data that admit efficient operations. Choice of structure trades off time complexity, space complexity, and cache behaviour for each operation.

## Key formulas

* Big-O: $f(n) = O(g(n)) \iff \exists c, n\_0.\ f(n) \le c g(n)$ for $n \ge n\_0$
* Amortised cost: $\sum\_i \hat c\_i \ge \sum\_i c\_i$ (potential method)
* Hash-table load factor: $\lambda = n/m$
* Balanced BST height: $O(\log n)$