The solution to the recurrence T(n) = 4T(n/2) + n turns out to be T(n) = e(n). Show that a substitution proof with the assumption T(n) ≤ cn fails. Then show how to subtract a lower-order term to make a substitution proof work.
![Question 1)
4T(n/2) + n turns out to be T(n)
The solution to the recurrence T(n)
that a substitution proof with the assumption T(n) ≤ cn² fails. Then show how to subtract
a lower-order term to make a substitution proof work.
=
=
(n²³).
. Show](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F165f5551-99fc-4800-9810-1597ce53807c%2F691f64de-0dab-4036-8419-171420988669%2F26m6atp_processed.jpeg&w=3840&q=75)
![¹ If there exists a constant k ≥ 0 such that f(n)
=
log a
k
loga, k+1.
lg n), then T(n) = O(n lg 'n)
Ⓒ(n](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F165f5551-99fc-4800-9810-1597ce53807c%2F691f64de-0dab-4036-8419-171420988669%2Fs2yxqc_processed.jpeg&w=3840&q=75)
![](/static/compass_v2/shared-icons/check-mark.png)
Required Proof:
Assuming T(n) < c*n^2 for some constant c, we can substitute it in the recurrence relation to get:
T(n) = 4T(n/2) + n < 4c(n/2)^2 + n = cn^2 + n
Since we want to prove that T(n) = O(n^2), we need to show that there exist constants c' and n0 such that T(n) <= c'n^2 for all n >= n0. However, we can see that this is not possible using the above inequality because cn^2 + n will always be greater than c'n^2 for any constant c' when n is sufficiently large. Therefore, the assumption that T(n) < c*n^2 fails to prove that T(n) = O(n^2).
To make a substitution proof work, we can subtract a lower-order term from T(n) before assuming T(n) < c*n^2. Let T'(n) = T(n) - an^b, where b > 2 and a is a constant to be determined later. Substituting T'(n) in the recurrence relation, we get:
T'(n) + an^b = 4[T'((n/2))] + n
= 4[(T(n/2) - a(n/2)^b)] + n
= 4T'(n/2) + 2an^b + n
Subtracting an additional an^b term from both sides, we get:
T'(n) = 4T'(n/2) + (n - an^b) <= 4c(n/2)^2 + (n - an^b) = cn^2 + (1 - 4a/4^(b-1))n^b
For the above inequality to hold, we need 1 - 4a/4^(b-1) to be negative, which implies that a > 4^(b-1)/4. Therefore, we can choose a = 1/4^(b-2) and get:
T'(n) <= cn^2 - n^(b-2)
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
![Blurred answer](/static/compass_v2/solution-images/blurred-answer.jpg)
![Database System Concepts](https://www.bartleby.com/isbn_cover_images/9780078022159/9780078022159_smallCoverImage.jpg)
![Starting Out with Python (4th Edition)](https://www.bartleby.com/isbn_cover_images/9780134444321/9780134444321_smallCoverImage.gif)
![Digital Fundamentals (11th Edition)](https://www.bartleby.com/isbn_cover_images/9780132737968/9780132737968_smallCoverImage.gif)
![Database System Concepts](https://www.bartleby.com/isbn_cover_images/9780078022159/9780078022159_smallCoverImage.jpg)
![Starting Out with Python (4th Edition)](https://www.bartleby.com/isbn_cover_images/9780134444321/9780134444321_smallCoverImage.gif)
![Digital Fundamentals (11th Edition)](https://www.bartleby.com/isbn_cover_images/9780132737968/9780132737968_smallCoverImage.gif)
![C How to Program (8th Edition)](https://www.bartleby.com/isbn_cover_images/9780133976892/9780133976892_smallCoverImage.gif)
![Database Systems: Design, Implementation, & Manag…](https://www.bartleby.com/isbn_cover_images/9781337627900/9781337627900_smallCoverImage.gif)
![Programmable Logic Controllers](https://www.bartleby.com/isbn_cover_images/9780073373843/9780073373843_smallCoverImage.gif)