Constants, sums and growths, worked on paper

Medium0 of 6 parts

Every question here is answered with a pencil, because every one of them is a step you have to be able to take without a machine. The first two ask you to produce the two numbers an asymptotic claim consists of. The rest are the small pieces of arithmetic that turn up inside a real analysis.

Throughout, $f(n) = 3n^2 + 5n + 100$ is the exact operation count of some procedure and $g(n) = n^2$ is the shape you are comparing it against. Recall the definition: $f(n) = O(g(n))$ means there are fixed numbers $c > 0$ and $n_0$ with $f(n) \le c\,g(n)$ for every $n \ge n_0$ .

Take $c = 4$ . Give the smallest whole number $n_0$ for which $3n^2 + 5n + 100 \le 4n^2$ holds at every $n \ge n_0$ .

Now hold $n_0 = 1$ instead. Give the smallest whole number $c$ for which $3n^2 + 5n + 100 \le c\,n^2$ holds at every $n \ge 1$ .

Evaluate $\sum_{i=1}^{n-1} i$ , the worst-case comparison count of insertion sort, as an expression in $n$ .

in terms of n

A doubling experiment gives a time ratio of 8 between each size and the one before it. Assuming the cost has the form $c\,n^b$ , give $b$ .

Rank two growths. Give the smallest whole number $n$ from which $n^{1.5} \ge n\log_2 n$ holds at that value and at every larger one.

Using $H_n \approx \ln n + 0.5772$ , estimate $H_{1000}$ . Give your answer to two decimal places.