Recurrences

Single correct

• A$T(n) = \Theta(n \log\log n)$
• B$T(n) = \Theta(n \log n)$
• C$T(n) = \Theta(n^2 \log n)$
• D$T(n) = \Theta(n^2 \log\log n)$

One or more correct

• A$f(2^n - 1) = 2^n - 1$
• B$f(2^n) = 1$
• C$f(5 \cdot 2^n) = 2^{n+1} + 1$
• D$f(2^n + 1) = 2^n + 1$

Answer key coming soon

Single correct

• A$T(n) = \Theta(n^{5/2})$
• B$T(n) = \Theta(n \log n)$
• C$T(n) = \Theta(n)$
• D$T(n) = \Theta((\log n)^{5/2})$

Answer key coming soon

Single correct

• AIf $f(n)$ is $n\log_2(n)$, then $T(n)$ is $\Theta(n\log_2(n))$.
• BIf $f(n)$ is $\dfrac{n}{\log_2(n)}$, then $T(n)$ is $\Theta(\log_2(n))$.
• CIf $f(n)$ is $O(n^{\log_b(a) - \epsilon})$ for some $\epsilon > 0$, then $T(n)$ is $\Theta(n^{\log_b(a)})$.
• DIf $f(n)$ is $\Theta(n^{\log_b(a)})$, then $T(n)$ is $\Theta(n^{\log_b(a)})$.

Answer key coming soon

Single correct

• A$\Theta(\log \log n)$
• B$\Theta(\log n)$
• C$\Theta(\sqrt{n})$
• D$\Theta(n)$

Answer key coming soon

Numerical answer

Answer key coming soon

Numerical answer

Answer key coming soon