Quiz on Asymptotic Notation and Recurrence Relations

The sum $\sum_{i=1}^{k} i$ is equal to $\frac{k(k+1)}{2}$, which is $\Theta(k^2)$. Here, $k = \lfloor \log n \rfloor$, so the sum is $\Theta((\log n)^2)$. Since $\Theta((\log n)^2)$ is the same as $O((\log n)^2)$, the claim is true. Note that $\log(n)^2$ is often written as $\log^2 n$.

$4^{\log_2 n} = (2^2)^{\log_2 n} = (2^{\log_2 n})^2 = n^2$.

The notation $\Omega(g(n))$ means strictly greater growth (lower bound that is not tight). Since $n!$ grows much faster than $2^n$ (as discussed in previous questions), the limit of $n!/2^n$ is $\infty$. Thus $n! = \Omega(2^n)$ is true.

For non-negative $f, g$, we have $\frac{1}{2}(f(n) + g(n)) \leq \max(f(n), g(n)) \leq f(n) + g(n)$. Since the maximum is bounded above and below by constant multiples of the sum, they are asymptotically equivalent.

Expanding the recurrence gives $T(n) = \sum_{i=1}^n \frac{1}{i}$. This is the $n$-th harmonic number $H_n$, which is known to grow as $\ln n + \gamma$ (where $\gamma$ is the Euler-Mascheroni constant). Thus, it is $\Theta(\log n)$.