| CPSC 327 | Data Structures and Algorithms | Spring 2024 |
Order functions by growth rate.
Simplify the given functions down to something recognizable. "Recognizable" is one of the common functions $1$, $\log n$, $n$, $n \log n$, $n^2$, $2^n$, $n!$; related generalized versions like $\log^c n$, $n^c$ and $b^n$; and products of these terms like $n^3 \log n$ or $n 2^n$. You can then often use the ordered list of common functions from class to figure out the ordering, either because you've simplified the function down to one of the common functions or because you can factor out common terms. For example, to determine whether $n^3$ is slower or faster-growing than $n^2 \log n$, factor out the common $n^2$ — now you are comparing $n^2 n$ and $n^2 \log n$. The list of common functions can be used to determine that $n$ grows faster than $\log n$, and thus $n^3$ grows faster than $n^2 \log n$.
Use the sums table to find $\Theta$ for a sum (thus simplifying the sum), and use the log and exponent rules to simplify functions involving logs and exponents. You can't necessarily assume that $\log f(n) = \Theta(\log n)$ or that $\sum_{i=0}^{n} f(i) = \Theta(f(n))$.
Give the big-Oh for code involving loops and nested loops.
Show your work — write the sum(s) corresponding to the loop(s), then deal with the sums one at a time. Don't only write the final big-Oh without any indication of how you got there.
While you can always use the sums table to determine the $\Theta$ (as long as the function being summed has the right form), it is worth recognizing a key shortcut: when each term is the same (i.e. the same amount of work is done in each repetition), the value of the sum reduces to a multiplication — the number of repetitions times the work per repetition. You can recognize this property in a sum when the $f(i)$ in $\sum_{i} f(i)$ doesn't actually involve $i$. In this case, skip the table and just do the multiplication.
Some useful math relating to sums:
The sums table does not work for functions containing
addition or subtraction. But you can rewrite the sum in two
pieces:
$\sum (a+b) = \sum a + \sum b$ and $\sum (a-b) =
\sum a - \sum b$.
The sums table is for $\sum_{i=1}^{n} f(i)$. For a sum that doesn't start at 1, keep in mind that $\sum_{i=j}^{n} f(i) = \sum_{i=1}^{n} f(i) - \sum_{i=1}^{j-1} f(i)$.
$O(f(n)-g(n)) = O(f(n))$ — subtracting just makes the value smaller, and what was an upper bound for $f(n)$ will still be an upper bound for something smaller than $f(n)$. So you can drop subtracted terms.
If $f(i)$ involves subtraction, a change of sum variable can be useful. (Consider this if $f(i+1) < f(i)$, that is, the terms of the sum are decreasing.) For example, $\sum_{i=1}^{n} (n-i)$ would be better written as $\sum_{j=0}^{n-1} j$ — observe that $\sum_{i=1}^{n} (n-i) = ( n-1 ) + ( n-2 ) + ( n-3 ) + ( ... ) + ( n-n )$, which can be rewritten as $0 + 1 + 2 + ... + (n-1)$, a pattern more simply described by $\sum_{j=0}^{n-1} j$.