MA005: Calculus I

Sometimes we want to compare the asymptotic behavior of two systems or functions for large values of $\mathrm{x}$, and l'Hô pital's Rule can be a useful tool. For example, if we have two different algorithms for sorting names, and each algorithm takes longer and longer to sort larger collections of names, we may want to know which algorithm will accomplish the task more efficiently for really large collections of names.

Example 4: Algorithm A requires $\mathrm{n} \cdot \ln (\mathrm{n})$ steps to sort $n$ names and algorithm $B$ requires $\mathrm{n}^{1.5}$ steps. Which algorithm will be better for sorting very large collections of names?

Solution: We can compare the ratio of the number of steps each algorithm requires, $\frac{\mathrm{n} \cdot \ln (\mathrm{n})}{\mathrm{n}^{1.5}}$, and then take the limit of this ratio as n grows arbitrarily large: $\lim \limits_{n \rightarrow \infty} \frac{n \cdot \ln (n)}{n^{1.5}}$. If this limit is infinite, we say that $\mathrm{n} \cdot \ln (\mathrm{n})$ "grows faster" than $\mathrm{n}^{1.5}$. If the limit is $0$ , we say that $\mathrm{n}^{1.5}$ grows faster than $\mathrm{n} \cdot \ln (\mathrm{n})$. Since $\mathrm{n} \cdot \ln (\mathrm{n})$ and $\mathrm{n}^{1.5}$ both grow arbitrarily large when $\mathrm{n}$ is large, we can algebraically simplify the ratio to $\frac{\ln (\mathrm{n})}{\mathrm{n}^{0.5}}$ and then use L'Hopital's Rule:

$\lim \limits_{n \rightarrow \infty} \frac{\ln (n)}{n^{0.5}}=\lim \limits_{n \rightarrow \infty} \frac{1 / n}{0.5 n^{-0.5}}=\lim \limits_{n \rightarrow \infty} \frac{2}{\sqrt{n}}=0$

$\mathrm{n}^{1.5}$ grows faster than $\mathrm{n} \cdot \ln (\mathrm{n})$ so algorithm $\mathrm{A}$ requires fewer steps for really large sorts.

Practice 3: Algorithm $A$ requires $\mathrm{e}^{\mathrm{n}}$ operations to find the shortest path connecting $\mathrm{n}$ towns, algorithm $B$ requires $100 \cdot \ln (\mathrm{n})$ operations for the same task, and algorithm $\mathrm{C}$ requires $\mathrm{n}^{5}$ operations. Which algorithm is best for finding the shortest path connecting a very large number of towns? Worst?