Figuring out which functions are Big-O of other functions (of a of 9 different functions). Where do I start?

Question

Problem

I need to arrange the following functions in order, so that each function is big-oh of the next function.

Functions

Attempt @ Solution

1. Understanding: I don't understand what to do here. My best guess is to determine what each function is Big-Oh of, and then rank the functions in order of magnitude of Big-Oh. Is that a way to start?

Answer 1

The problem is essentially to rank the nine functions in order of increasing growth rates. You know, for instance, that $2^n$ grows faster than $n^2$, and hence that $n^2$ is $O(2^n)$; thus, $n^2$ will come somewhere before $2^n$ in your ranking.

The first five are already fairly basic functions: you should definitely know the proper order for $n!$, $2^n$, $n^2$, $\sqrt n$, and you should probably know where $\log_2n$ fits into that list. The other four will require some work; in each case it would be helpful to find a simple function $g(n)$ such that the given function is $\Theta\big(g(n)\big)$, i.e., both $O\big(g(n)\big)$ and $\Omega\big(g(n)\big)$.

I’ll get you started on one of them and add some hints for the rest. From the formula for the sum of a geometric series you know that $$\sum_{i=0}^n2^i=\frac{2^{n+1}-2^0}{2-1}=2^{n+1}-1\;.$$ This suggests that you should try to show that $\sum_{i=0}^n2^i$ is $\Theta(2^{n+1})$, since for large $n$ that $-1$ is going to be insignificant.

You may have to dig it out, but there’s a known formula for the sum of the first $n$ perfect squares; you can use that to work out the growth rate of $\sum_{i=0}^ni^2$. Use the properties of logarithms to simplify $\sum_{i=1}^n\log_2i$; it’s the log base $2$ of what function of $n$? As for the last one, what limit does it approach as $n\to\infty$?

Answer 2

For a starter, the last function is the slowest, because you can take (numerator is $a(n)$, denominator $d(n)$:

$$ \frac{a(n)}{d(n)}\leq \frac{(n+3)^3}{(n-3)^3} \leq \frac{3n^3}{\frac{n^3}{3}}=9=O(1) $$

The rest of your functions are $\omega(1)$, i.e. the tend to infinity as $n \to \infty$