Recurrences

Single correct

• A$T_1(n) = \Theta(n^2)$
• B$T_1(n) = \Theta(n^2 \log_2 n)$
• C$T_1(n) = \Theta(n^{\log_4 5})$
• D$T_1(n) = \Theta(n^{\log_4 5} \log_2 n)$

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(n^2 2^n)$
• B$T(n) = \Theta(n 2^n)$
• C$T(n) = \Theta((\log n)^2 2^n)$
• D$T(n) = \Theta(4^n)$

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)$

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)$

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_a \log_b n)$
• B$\Theta(\log_{ab} n)$
• C$\Theta(\log_b \log_a n)$
• D$\Theta(\log_2 \log_2 n)$

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

Single correct

• A$T(n) = 2T(n/2) + cn$
• B$T(n) = T(n-1) + T(1) + cn$
• C$T(n) = 2T(n-1) + cn$
• D$T(n) = T(n/2) + cn$

Single correct

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

Single correct

• A$T(n) = 2T(n-2) + 2$
• B$T(n) = 2T(n-1) + n$
• C$T(n) = 2T(n/2) + 1$
• D$T(n) = 2T(n-1) + 1$

Answer key coming soon