Comparative Growth
Suppose you have a list with a million items on it and you need to sort them. There are a dozen sorting algorithms you can chose from. Which one is best for your situation?
Measuring the efficiency of algorithms is an important topic in computer science and algorithm design. This is usually done by thinking about how many operations it would take for an algorithm to process an input set with $n$ elements. You often can't do this exactly since it depends on the specific input. For example, if your set was already sorted then it would probably take fewer steps than a set with the numbers sorted backwards from the order you needed. To resolve this, algorithm designers usually look at the worst case scenario. For example, the bubble sort method takes, on average, $n^2$ operations where the merge sort method takes $n \log n$. That's good to know but it doesn't answer the question, "Which one is better?"
One way to answer this is to look at the ratio of the two speeds as $n\to\infty$. Here's the rule that we'll use:
Relative Growth
or
$$\lim\limits_{x\to\infty}\frac{g(x)}{f(x)} = 0$$The functions grow at the same rate if and only if
$$\lim\limits_{x\to\infty}\frac{g(x)}{f(x)} = k$$where $k$ is a constant. Otherwise we say that $g$ frows faster than $f$.
So how do our two sort algorithms compare? Our definition says that we need to look at their ratio, let $n$ go to infinity and see what happens.
$$\begin{aligned} \lim\limits_{x\to \infty}\frac{\text{bubble sort}}{\text{merge sort}} &= \lim\limits_{x\to \infty}\frac{n^2}{n \log n} \\ &= \lim\limits_{x\to \infty}\frac{n}{\log n} \end{aligned}$$This evaluates to $\infty / \infty$ so we can apply l'Hospital's Rule.
$$\begin{aligned} \lim\limits_{x\to \infty}\frac{\text{bubble sort}}{\text{merge sort}} &= \lim\limits_{x\to \infty}\frac{1}{\frac{1}{\ln(10) \log n}} \\ &= \lim\limits_{x\to \infty}\ln(10) \log n \\ &= \infty \end{aligned}$$Referring back to our definition, we can conclude that the bubble sort method's average number of operations grows faster than the merge sort which makes it, again on average, less efficient.
Exercises
 : shows the complete answer. |  : gives a hint |
 : plays a video solution |  : shows just the final answer |
 : these are important examples that illustrate new concepts, you should be sure to review the solutions to these questions | |
Explorations
Determine which of each pair of functions increases faster.
|
|
|
- In computer science, it's a common practice to ignore a constant multiple when comparing the times to algorithms. To see why, compare the growth rates of $f(x)$ and $kf(x)$ where $k$ is a positive constant.
- Show that if the degree of one polynomial is higher than the other then that polynomial grows faster, i.e. the growth rate is determined exclusively by comparing the terms with the greatest exponents. To do this, let $p(x) = a_mx^m + a_{m-1}x^{m-1} + ... + a_1x + a_0$ and $q(x) = b_nx^n + b_{n-1}x^{n-1} + ... + b_1x + b_0$ then show that $p$ increases faster if $m > n$ and they increase at the same rate if $m = n$.
- Show that an exponential function with base greater than 1 always exceeds a polynomial function by comparing $f(x) = a^x$ to $g(x) = x^n$.
- Compare the growth rates of $f(x) = \ln x$ and $g(x) = \ln(x + a)$ for any constanat $a$.
- Sort the following functions from fastest growing to slowest: $2^x$, $\log_2 x$, $x^2$ and $x \log_2 x$.
- Sort the following functions from fastest growing to slowest (some may be the same): $3^x$, $5$, $e^x$, $x^x$, $x^{10}$ and $x^5$.
Icons courtesy of icons8.com
Compare the growth rates of $f(n) = n^2$ and $g(n) = n$.
$$\begin{aligned} \lim\limits_{x\to \infty} \frac{f(n)}{g(n)} &= \lim\limits_{x\to \infty}\frac{n^2}{n} \\ &= \lim\limits_{x\to \infty} n \\ &= \infty \end{aligned}$$
So $f(n) = n^2$ grows faster.
Compare the growth rates of $f(n) = \log n$ and $g(n) = \ln n$.
Use the change of base formula to evaluate the limit.
Compare the growth rates of $f(n) = \log n$ and $g(n) = \ln n$.
Use the change of base formula to evaluate the limit.
$$\begin{aligned} \lim\limits_{x\to \infty} \frac{f(n)}{g(n)} &= \lim\limits_{x\to \infty}\frac{\log n}{\ln n} \\ &= \lim\limits_{x\to \infty}\frac{\frac{\ln n}{\ln 10}}{\ln n} \\ &= \lim\limits_{x\to \infty}\frac{1}{\ln 10} \\ &= \frac{1}{\ln 10} \end{aligned}$$Because the limit is a constant, the two functions are changing at the same rate.
Compare the growth rates of $f(n) = n^{100}$ and $g(n) = e^n$.
$$\begin{aligned} \lim\limits_{x\to \infty} \frac{f(n)}{g(n)} &= \lim\limits_{x\to \infty}\frac{n^{100}}{e^n} \\ &= \lim\limits_{x\to \infty}\frac{100n^{99}}{e^n} \\ &= \lim\limits_{x\to \infty}\frac{100 \cdot 99 n^{98}}{e^n} \\ &= ... \\ &= \lim\limits_{x\to \infty}\frac{100!}{e^n} \\ &= 0 \end{aligned}$$
So $g(n) = e^x$ grows faster.
In computer science, it's a common practice to ignore a constant multiple when comparing the times to algorithms. To see why, compare the growth rates of $f(x)$ and $kf(x)$ where $k$ is a positive constant.
$$\lim\limits_{x\to\infty}\frac{kf(x)}{f(x)} = \lim\limits_{x\to\infty} k = k$$Because the limit is constant, the two functions are growing at the same relative rate.
Show that an exponential function with base greater than 1 always exceeds a polynomial function by comparing $f(x) = a^x$ to $g(x) = x^n$.
$$\begin{aligned} \lim\limits_{x\to\infty}\frac{f(x)}{g(x)} &= \lim\limits_{x\to\infty}\frac{a^x}{x^n} \\ &= \lim\limits_{x\to\infty}\frac{a^x \ln a}{nx^{n-1}} \\ &= \lim\limits_{x\to\infty}\frac{a^x \ln^2 a}{n(n-1)x^{n-2}} \\ &... \\ &= \lim\limits_{x\to\infty}\frac{a^x \ln^n a}{n!} \\ &= \infty \end{aligned}$$
In the end, $n!$ is potentially large but it's still constant. This makes the exponential function the faster grower of the two.
Sort the following functions from fastest growing to slowest: $2^x$, $\log_2 x$, $x^2$ and $x \log_2 x$.
$2^x$, $x^2$, $x \log_2 x$ and $\log_2 x$
Sort the following functions from fastest growing to slowest (some may be the same): $3^x$, $5$, $e^x$, $x^x$, $x^{10}$ and $x^5$.
$x^x$, $3^x$, $e^x$, $x^{10}$, $x^5$ and $5$
$3^x$ and $e^x$ both grow at the same relative rate and $x^{10}$ and $x^5$ also grow at the same rate.
