알고리즘의 시간 복잡도 설명에 사용하는 표기법. $f(n) = O(n^2)$ 꼴로 쓴다.

## On notation

$\Theta(g(n))$ is a set:

> Because $\Theta(g(n))$ is a set, we could write "$f(n) \in \Theta(g(n))$" to indicate that $f(n)$ is a member of $\Theta(g(n))$. Instead, we will usually write "$f(n)=\Theta(g(n))$" to express the same notion.[^1]

Minor abusing:

> Since any constant is a degree-0 polynomial, we can express any constant function as $\Theta(n^0)$, or $\Theta(1)$. This latter notation is a minor abuse, however, becuase the expression doesn not indicate what variable is tending to infinity. We shall often use the notation $\Theta(1)$ to mean either a constant or a constant function with respect to some variable.
>
> (The real problem is that our ordinary notation for functions does not distinguish functions from values. in [Lambda calculus](/pages/Lambda%20calculus.txt), the parameters to a function are clealy specified: the function $n^2$ could be written as $\lambda n.n^2$, or even $\lambda r.r^2$. Adopting a more rigorous notation, howevery, would complicate algebraic manipulations, and so we choose to tolerate the abuse.)[^1]

## $\Theta$-notation (Big Theta notation)

정의:[^1]

> For a given function $g(n), we denote by $\Theta(g(n))$ the set of functions
>
> $\Theta(g(n))$ = { $f(n)$ such that there exist positive constants $c_1$, $c_2$, and $n_0$ such that $0 \leq c_1 g(n) \leq f(n) \leq c_2 g(n)$ for all $n \geq n_0$ .

설명:[^1]

> A function $f(n)$ belongs to the set $\Theta(g(n))$ if there exist positive constants $c_1$ and $c_2$ such that it can be "sandwiched" between $c_1 g(n)$ and $c_2 g(n)$, for sufficiently large $n$. … In other words, for all $n \geq n_0$, the function $f(n)$ is equal to $g(n)$ to within a constant factor. We say that $g(n)$ is an ***asymptotically tight bound*** for $f(n)$.

## $\Omega$-notation (Big Omega notation)

## O-notation (Big O notation)

## Footnotes

[^1]: Chapter 3, <Introduction to algorithms>