Analysis on the asymptotic behavior of memory usage/runtime $R$ as the input size $N$ grows. The following definitions hold for all $N > N_0$, for sufficiently large $N_0$, and positive coefficients $c_i$.
Big Theta $\Theta(f)$. Class of functions that grow at the same rate as $f$.
$$ R(N) \in \Theta(f(N)) \iff c_1f(N) \leq R(N) \leq c_2f(N) $$
Big Omega $\Omega(f)$. Class of functions for which all grow at least as fast as $f$.
$$ R(N) \in \Omega(f(N)) \iff c_1f(N) \leq R(N) $$
Big O $\mathcal{O}(f)$. Class of functions for which all grow at most as fast as $f$.
$$ R(N) \in \mathcal{O}(f(N)) \iff R(N) \leq c_2f(N) $$
$$ R\in \Omega (f) \text{ and } R\in \mathcal{O}(f) \rightarrow R \in \Theta (f) $$
Asymptotic analysis disregards lower order terms, constants, and bases of logarithms when determining the complexity of an algorithm.
Instead of looking at how a single operation performs on an input of size $N$, amortized analysis looks at how an operation performs, on average, over $N$ executions on an input of size $N$.
Abstract data type which organizes connected components into partitions of a set of $N$ objects.
public interface DisjointSets {
void connect(int p, int q);
boolean isConnected(int p, int q);