2025-02-06 -- asymptotics and derivatives
-----------------------------------------

You are asked to order f(n) and g(n) by their asymptotic behavior
(big-O notation, or actually little-o). You use the limit rule:

- Take the limit of f(n) / g(n) for n -> infinity.
  - 0 means little o.
  - Infinity means little omega.
  - Some real from (0, infinity) means big O.

You might have to use the rule of L'Hospital, so you must know
how to take derivatives. Remember the derivation rules:

- (u + v)' = u' + v'
- (u - v)' = u' - v'
- (u * v)' = u' * v + u * v'
- (u / v)' = (u' * v - u * v') / v^2
- (u(v))'  = u'(v) * v'

Some useful derivatives (over x):

- log_2 x   -> 1 / (x * ln 2)
- log_2^a x -> (a * ln^(a-1) x) / (x * ln^a 2)
- x^a       -> a * x^(a-1)
- a^x       -> a^x * ln a
- sqrt(x)   -> 1 / (2 * sqrt(x))
- x^a * log_2^b x
  -> (x^(a-1) * ln^(b-1) x * (a * ln x + b)) / ln^b 2

And some pre-sorted functions, where 0 < a < b, 0 < alpha < beta,
1 < A < B, and each line is in little o of the next:

- log^alpha n
- log^beta n
- n^a
- n^a * log^alpha n
- n^b
- A^n
- n^a * A^n
- B^n
- n!

Also, if f_1 is in O(g_1) and f_2 is in O(g_2), then:

- f_1 + f_2 is in O(max{g_1, g_2}),
- f_1 * f_2 is in O(g_1 * g_2).

For implications, remember:

- little o     is like <,
- big    O     is like <=,
- little omega is like >,
- big    Omega is like >=,
- big    Theta is like =.