> 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.md).

# computer\_science

## Basic idea

The study of computation: what can be computed, how efficiently, and with which abstractions. Spans theory (complexity, computability), systems (OS, distributed), languages, data structures, and AI.

## Key formulas

* Big-O: $f(n) = O(g(n)) \iff \exists c, n\_0.\ \forall n \ge n\_0.\ f(n) \le c, g(n)$
* Master theorem: $T(n) = a T(n/b) + f(n)$
* Shannon entropy: $H(X) = -\sum\_i p\_i \log p\_i$
* Church-Turing thesis: computable = Turing-computable