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))$$

logo