Quiz on Asymptotic Notation and Recurrence Relations

Let $u = \log n$. We are comparing $\log u$ and $\sqrt{u}$. Since the logarithm of a variable grows slower than any positive power of that variable, $\log u = o(\sqrt{u})$. Thus the statement is true.

To check this, examine the limit of the ratio: $\frac{n^{0.99} \log n}{n} = \frac{\log n}{n^{0.01}}$. Since polynomial growth ($n^{0.01}$) beats logarithmic growth, the limit is 0. Thus, $n^{0.99} \log n = o(n) \subseteq O(n)$.

The highest degree term is $3n^4$. Thus the function is $\Theta(n^4)$. It grows strictly faster than $n^3$, so it cannot be $\Theta(n^3)$.

Dies ist eine arithmetische Reihe, die bis zu $\approx \sqrt{n}$ Terme aufsummiert, wobei der größte Term $\approx \sqrt{n}$ ist. Die Summe skaliert mit $(\sqrt{n})^2 = n$.

This is the 'transpose symmetry' property of asymptotic notation. If $f$ is upper-bounded by $g$, then $g$ is lower-bounded by $f$.