Recurrences

One or more correct

• A$T(n) = T(n-1) + 1, \quad T(1) = 1$
• B$T(n) = 2T\left(\frac{n}{2}\right) + 1, \quad T(1) = 1$
• C$T(n) = 2T\left(\frac{n}{2}\right) + n, \quad T(1) = 1$
• D$T(n) = T(n-1) + n, \quad T(1) = 1$

Single correct

• A$T(n) = \Theta(2^n)$
• B$T(n) = \Theta(n2^n)$
• C$T(n) = \Theta(3^n)$
• D$T(n) = \Theta(n3^n)$

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

Single correct

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