It's attached as a pdf

1 answer below »
Answered Same DayJul 05, 2021

Answer To: It's attached as a pdf

Tejas answered on Jul 05 2021
133 Votes
Assignment4
Q1. T(n) = 2, n = 1
T(n) = 2T(n - 1) + 2^n, n > 1
a. Substitution method
T(n) = 2T(n - 1) + 2^n
Expanding T(n
- 1) using the recurrence when n > 1,
T(n) = 2(2T(n - 2) + 2^(n - 1)) + 2^n
T(n) = 2^2 * T(n - 2) + 2^n + 2^n
T(n) = 2^2 * T(n - 2) + 2 * 2^n
For k = 2, we can generalize the above statement as:
T(n) = 2^k * T(n - k) + k * 2^n
Assume T(n) = O(cn * 2^n) where c > 0, a constant
So, T(n) = 2^2 * c(n - 2) * 2^(n - 2) + 2 * 2^n
T(n) = cn * 2^n - 2 * 2^n + 2 * 2^n
T(n) = cn * 2^n
So, T(n) = O(n * 2^n)
b. Induction proof
Base case: n = 2
T(2) = 2 * T(1) + 2^2
T(2) = 2 * 2 + 4……………..Given T(1) = 2
T(2) = 8
O(n * 2^n) for n = 2 is 2 * 2^2 = 8. Hence, the base case is satisfied T(n) = O(n * 2^n)
Inductive step: Assume the above recurrence relation and asymptotic notation is true for
all k <= n. So, T(n) = O(n * 2^n).
At k = n + 1
T(n + 1) = 2T(n + 1 - 1) + 2^(n + 1)
T(n + 1) = 2T(n) + 2^(n + 1)
But T(n) = O(n * 2^n)
T(n + 1) = 2(n * 2^n) + 2^(n + 1)
T(n + 1) = n * 2^(n + 1) + 2^(n + 1)
T(n + 1) = (n + 1) * 2^(n + 1)
T(n + 1) = O((n + 1) * 2^(n + 1))
Hence, proved
Therefore, the solution from part a is correct as proved by induction.
Q2. T(n) = 1, n = 1
T(n) = 4, n = 2
T(n) = T(n - 2) + n^2, n > 2
a. T(n) = T(n - 2) + n^2
Expanding T(n - 2) using the recurrence when n > 1,
T(n) = (T(n - 4) + (n - 2)^2) + n^2
Similarly expanding T(n - 4),
T(n) = ((T(n - 6) + (n - 4)^2) + (n - 2)^2 + n^2)
We can generalize the above...
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here