the limit definition of growth rates

Often the fastest way to compare two functions is not to fiddle with witness constants but to watch what their ratio does as n races off to infinity. If you put f on top and g on the bottom, the single number that the fraction f(n)/g(n) settles toward tells you almost everything about their relative growth.

Here is the dictionary, assuming the limit L of f(n)/g(n) as n goes to infinity exists. If L = 0, then f grows strictly slower, so f = o(g) (and hence f = O(g)). If L is infinity, then f grows strictly faster, so f = omega(g) (and hence f = Omega(g)). If L is a positive finite constant, then f and g grow at the same rate, so f = Theta(g). So a single limit can hand you o, omega, or Theta in one stroke. For example, comparing f = 3n^2 and g = n^2 gives ratio 3, a positive constant, so 3n^2 = Theta(n^2); comparing f = n and g = n^2 gives ratio 1/n which goes to 0, so n = o(n^2).

Two honest caveats. First, the limit must actually exist; for oscillating functions it may not, and then you must fall back on the witness-constant definitions directly (Big-O and Big-Omega never require a limit). Second, computing the limit can need calculus tools, most usefully L'Hopital's rule, which is exactly how one shows (log n)/n tends to 0 or n/(2^n) tends to 0. When it applies, though, the limit test is the quickest route to a clean asymptotic comparison.