Two Questions with Homogeneous Recurrences and Master Theorem

Question

1) Solve the recurrence T(n) + 6T(n − 1) + 12T(n − 2) + 8T(n-3) = 0 given the initial conditions T(0) = 1, T(1) = −2, and T(2) = 8.

2) Solve the recurrence given by:

T(n) = a for n ≤ 2
T(n) = 7T(n/2) + bn2 , n>2

Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

This is the first case of Master Theorem from theory:
We have the initial conditions: a=7, b=2, f(n)=b*n2 and log_b⁡a = log_2⁡(7) > 2 (the power of n from f(n)).
In our conditions (a=7,b=2…) this leads that T(n)= O(n^log_2⁡(7) )...

This is only a preview of the solution. Please use the purchase button to see the entire solution

$13.00 for this solution