# Proving asymptotics using limits

Let $$f(n)$$ and $$g(n)$$ be positive functions.

Let $$h(n) = f(n) / g(n)$$.

1. If g(n) increases at a faster rate than f(n), it is the upper bound for f(n)

$$If \lim_{n \to +\infty} h(x) = 0, then f(n) \in O(g(n)) \land f(n) \neq \Omega(g(n))$$

2. If g(n) increases at same rate to f(n), it is the tight bound for f(n)

$$If \lim_{n \to +\infty} h(x) = b, where\ b > 0, then f(n) \in \Theta(g(n))$$

3. If g(n) increases at a slower rate than f(n), it is the lower bound for f(n)

$$If \lim_{n \to +\infty} h(x) = \infty, then f(n) \in \Omega(g(n)) \land f(n) \neq O(g(n))$$