We start with some exercises testing understanding of Landau notation.
Section20.6Exercises
1
Show that \(\sigma(n)\) is \(O(n^2)\) (compare to the sum of all integers).
2
Use the formula for the sum of the first \(n\) perfect squares (often encountered in a Transition to Proof course or when first doing definite integrals in Calculus) and the previous exercise to show that the average value of \(\sigma(n)\) is Big Oh of \(n^2\). (This can be loosey-goosey.)
3
Show that if \(g\) and \(h\) are both \(O(f)\) for some \(f\), then \(g+h\) is also \(O(f)\).
4
Show that if \(g\) is \(O(f)\) for some \(f\), then if \(c>0\) we have that \(g\) is \(O(cf)\) and \(cg\) is \(O(f)\).
5
Show that if \(g\) is \(O(f)\) for some \(f\) and if \(f(x)\leq h(x)\) for \(x\) large enough, then \(g\) is also \(O(h)\).
6
Find a formula for the average value of the \(u\) and \(N\) functions (up through \(n\)), where \(u(n)=1\) for all \(n\) and \(N(n)=n\) for all \(n\) (recall Definition 19.2.9).
7
Finish off all calculus details in the argument in 20.2.3.
8
Finish the details of the proof that \(\tau\) is \(O(\sqrt[3]{x})\)
9
Show that \(\tau(n)\) is not \(O(1)\). (Hint: that means there is no constant \(C\) such that \(\tau(n)\leq C\) always.)
10
Why would it not contradict our theorem above that \(\frac{1}{n}\sum_{k=1}^n\tau(k)=O(\log(n))\) to say that \(\tau(n)\) is not \(O(\log(n))\)?
11
Show that \(\tau(n)\) is not \(O(\log(n))\). (Hint: look at numbers of the form \(6^k\), and compare \(\tau\) of these to any given multiple of the natural logarithm using calculus.)
12
Finish all calculus details of the proof of \(\sigma\)'s average size in 20.4.
13
Finish the details of the first computation of Big Oh in 20.4.2.
14
Find absolute bounds for \(\phi(n)\) (simple polynomial or log formulas in terms of \(n\)).
15
Use data, graphs, whatever to conjecture what type of growth the average value of \(\phi\) has up to \(n\). Is it logarithmic, linear, quadratic, exponential, something else? Bonus if you find a coefficient for the growth!