Question

1. Determine the asymptotic complexity of the function defined by the recurrence relation. Justify your solution using expansion/substitution and upper and/or lower bounds, when necessary. You may not use the Master Theorem as justification of your answer. Simplify and express your answer as $\Theta(n^k)$ or $\Theta(n^k \log_2 n)$ whenever possible. If the algorithm is exponential just give exponential lower bounds. a) $T(n) = T(n-3) + cn^5$, $T(0) = c^\prime$ b) $T(n) = T(n-3) + T(n-6) + T(n-7) + cn^3\log_2 n$, $T(0) = c^\prime$ c) $T(n) = 2T(n/2) + c$, $T(1) = c^\prime$

          1. Determine the asymptotic complexity of the function defined by the recurrence relation.
Justify your solution using expansion/substitution and upper and/or lower bounds, when
necessary. You may not use the Master Theorem as justification of your answer. Simplify
and express your answer as $\Theta(n^k)$ or $\Theta(n^k \log_2 n)$ whenever possible. If the algorithm is
exponential just give exponential lower bounds.
a) $T(n) = T(n-3) + cn^5$, $T(0) = c^\prime$
b) $T(n) = T(n-3) + T(n-6) + T(n-7) + cn^3\log_2 n$, $T(0) = c^\prime$
c) $T(n) = 2T(n/2) + c$, $T(1) = c^\prime$

1. Determine the asymptotic complexity of the function defined by the recurrence relation.
Justify your solution using expansion/substitution and upper and/or lower bounds, when
necessary. You may not use the Master Theorem as justification of your answer. Simplify
and express your answer as Θ(n^k) or Θ(n^k log2 n) whenever possible. If the algorithm is
exponential just give exponential lower bounds.
a) T(n) = T(n-3) + cn^5, T(0) = c^'
b) T(n) = T(n-3) + T(n-6) + T(n-7) + cn^3log2 n, T(0) = c^'
c) T(n) = 2T(n/2) + c, T(1) = c^'

Added by Allison B.

Question

Please give Ace some feedback