1814 WordsMar 14, 20148 Pages

Recurrences
(CLRS 4.1-4.2)
• Last time we discussed divide-and-conquer algorithms Divide and Conquer To Solve P: 1. Divide P into smaller problems P1 , P2 , P3 .....Pk . 2. Conquer by solving the (smaller) subproblems recursively. 3. Combine solutions to P1 , P2 , ...Pk into solution for P. • Analysis of divide-and-conquer algorithms and in general of recursive algorithms leads to recurrences. • Merge-sort lead to the recurrence T (n) = 2T (n/2) + n – or rather, T (n) = Θ(1) T( n ) + T( 2 n 2
If n = 1 ) + Θ(n) If n > 1
– but we will often cheat and just solve the simple formula (equivalent to assuming that n = 2k for some constant k, and leaving out base case and constant in Θ). Methods for solving recurrences 1. Substitution method 2. Iteration method • Recursion-tree method
• (Master method)
1
Solving Recurrences with the Substitution Method
• Idea: Make a guess for the form of the solution and prove by induction. • Can be used to prove both upper bounds O() and lower bounds Ω(). • Let’s solve T (n) = 2T (n/2) + n using substitution – Guess T (n) ≤ cn log n for some constant c (that is, T (n) = O(n log n)) – Proof: ∗ Base case: we need to show that our guess holds for some base case (not necessarily n = 1, some small n is ok). Ok, since function constant for small constant n. ∗ Assume holds for n/2: T (n/2) ≤ c n log n (Question: Why not n − 1?) 2 2 Prove that holds for n: T (n) ≤ cn log n T (n) = 2T (n/2) + n n n ≤ 2(c log ) + n 2 2 n = cn log + n 2 = cn log n − cn log 2 + n = cn log n − cn + n
So ok if c ≥ 1 • Similarly it can be shown that T (n) = Ω(n log n) Exercise! • Similarly it can be shown that T (n) = T ( Exercise! n 2
) + T(
n 2
) + n is Θ(n lg n).
• The hard part of the substitution method is often to make a good guess. How do we make a good (i.e. tight) guess??? Unfortunately, there’s no “recipe” for this one. Try

Related

## Term Paper

1304 Words | 6 PagesAmit Saklani TABLE OF CONTENTS: 1. Recurrence Relation 2. Recurrence : Substitution Method 3. Recurrence : Iterative Method 4. Examples to show Substitution Method 5. Examples

## Hernia Repair Essay

1520 Words | 7 PagesObjective: To compare the clinical recurrence rate with reoperation rate for recurrence after ventral hernia repair. Background: Reoperation is often used as an outcome measure after ventral hernia repair, but it is unknown whether reoperation rate renects the overall clinical risk for recurrence. Methods: The study cohort was recruited from the Danish Ventral Hernia Database and the Danish National Patient Registry during January I, 2007, to December 31, 2007. Inclusion criteria were primary umbilical/epigastric

## Depression Essay

9139 Words | 37 PagesJournal of Consulting and Clinical Psychology 2000, Vol. 68, No. 4, 615-623 Copyright 2000 by the American Psychological Association, Inc. 0022-006X/00/$5.00 DOI: 10.1037//0022-006X.68.4.615 Prevention of Relapse/Recurrence in Major Depression by Mindfulness-Based Cognitive Therapy John D. Teasdale Medical Research Council Cognition and Brain Sciences Unit Zindel V. Segal Centre for Addiction and Mental Health, Clarke Division, and University of Toronto J. Mark G. Williams University

## Effects of Asprin Essay

413 Words | 2 Pageskeeps breast tumor cells from growing and invading other tissues. Regular aspirin users have a lower risk of dying form breast cancer. Women who take aspirin regularly, their breast cancer goes into remission are about 50% less likely to suffer a recurrence or to die from the disease, according to new finding from “ongoing Nurses” Health study. The results, reported Tuesday in the journal of clinical oncology, are surprising because at least five large studies have shown that taking aspirin regularly

## Artifical Intelligent Essay

1035 Words | 5 PagesMath 471 Problem 1. Group Work #8 Fall 2011 (a): Find a recurrence relation for the number tn of bit strings of length n that contain three consecutive zeros. SOLUTION: We break up all of the bit strings of length n according to the following nonoverlapping cases: • Bit Strings Beginning with “1”: In this case, the three consecutive zeros must appear in the last n − 1 slots, and there are tn−1 bit strings that will have three consecutive zeros there. • Bit Strings Beginning with “01”: In

## Soy Benefits Essay

6771 Words | 28 Pagesthis on StumbleUpon Tweet about this Article Share this on Facebook more> * Email * Print 12 Istockphoto TUESDAY, December 8, 2009 (Health.com) — Women with breast cancer who eat more soy are less likely to die or have a recurrence of cancer than women who eat few or no soy products, according to a new study. In the past, physicians have often warned breast cancer patients not to eat soy. The new research represents "a complete turnaround" from the previous understanding

## Ranula Essay

5288 Words | 22 PagesManagement of ranula: Aspiration: Zhi et al., used aspiration in 11 infants (age less than 3 months) with oral ranula, nine of which recurred. This yield a recurrence rate of 82% no other complication were documented. He recommending conservative management for infants up to age of 1 year old and adequate period of observation for 6 months for spontaneous resolution after aspiration.(9) Marsupalization: A number of authors recommend marsupalization of ranula as preferred method of treatment

## Saran Essay

589 Words | 3 Pagesfor all items in a series 1. Click Open the series, and then click OK. 2. On the Appointment tab, change the subject or location options as required. 3. To change the recurrence options, on the Actions menu, click Recurrence, change the start time, end time, recurrence pattern, or range of recurrence as required, and then click OK. 4. Click Save and Close. * To change options for one item that is part of a series 1. Click Open this occurrence, and then click OK.

## Health Teachings Essay

658 Words | 3 Pageshome 2.To promote early recovery from the disease 3.To decrease stress that could cause the recurrence of the disease 4. Skin Care RATIONALE 1.Wash hands often, especially after using the bathroom. 2.Change wound dressings daily and aseptically. to prevent recurrence of infection. 1.it is an infection control practice to reduce the spread of infection 2. To prevent recurrence of infection. 4.Hygiene RATIONALE 1.Perform frequent mouth care with a soft toothbrush

## German Crdit Essay

903 Words | 4 Pagesinformation on the recurrence or non-recurrence of breast cancer amongst 285 patients. This data set is from a study to see if there is a recurrence of cancer based on various attributes. It includes 201 instances of one class and 84 instances of another class and 9 possible attributes (in addition to the class attribute). These are as follows (the numbers in parentheses represent the number of values that are possible for that attribute): Class no-recurrence-events, recurrence-events. age (9)

### Term Paper

1304 Words | 6 Pages### Hernia Repair Essay

1520 Words | 7 Pages### Depression Essay

9139 Words | 37 Pages### Effects of Asprin Essay

413 Words | 2 Pages### Artifical Intelligent Essay

1035 Words | 5 Pages### Soy Benefits Essay

6771 Words | 28 Pages### Ranula Essay

5288 Words | 22 Pages### Saran Essay

589 Words | 3 Pages### Health Teachings Essay

658 Words | 3 Pages### German Crdit Essay

903 Words | 4 Pages