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.

Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
icon
Related questions
Question
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
Transcribed Image Text: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
¹ 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
Transcribed Image Text:¹ 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
Expert Solution
Step 1: Required Proof

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

Trending now

This is a popular solution!

steps

Step by step

Solved in 2 steps

Blurred answer
Knowledge Booster
Recurrence Relation
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Similar questions
  • SEE MORE QUESTIONS
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education