Homework Help is Here – Start Your Trial Now!
Engineering
Computer Science
5. Here is a tree corresponding to T(64) for an unknown recurrence relation: 32+ lg 64 2+lg4 8+ lg 16 2+lg 4 2+lg4 8+ lg 16 2+lg4 7 7 7 7 7 7 7 7 Fill in the details for the corresponding recurrence relation: T(n) = T(1) = T(n/4) + Put scratch work below. Scratch work is not graded but may be used for regrade partial credit. and on the n-values we're analyzing. So as not to go off the deep end, let's consider the example again: Example 3.1. Suppose T(n) = 3T (n/5) + (2n + 1) with T(1) = 4. Let's examine T(n) where n = 5k for some k. To understand why there's a tree involved we can view the total time done as a very small tree, first with one node: T(n) We can expand this according to the recurrence relation, the tree still show- ing the total time: 2n+1 But when does it stop? The tree stops growing when we reach T(1) in the nodes because T(1) = 4 and no more recursion happens. If level i=0 is the top level then as the tree grows we see that level í has entries T(n/5) so the leaf level will happen when we reach T(1) which is when n/5=1 or i = log, n=k. Thus the kth level is the leaf level. Thus in total there are k+1 levels, 0, 1, ..., k, and in those levels: Count Time 2n+1 Level i=0 1 i=1 i=2 3 9 2()+1 2()+1 B i=k-1 i=k 3k-1 3k 4 Level Time 1(2n+1) 3º (2()+1) 3 (2()+1) 31 (2()+1) 9 (2()+1) 32 (2 ()+1) B 2()+13 (2 (5)+1) 3 (4) Thus the total time is the sum of the levels: T(n/5) T(n/5) T(n/5) Of course each of these leaves is its own problem, the tree still showing the total time. 2(n/5)+1 2n+1 2(n/5)+1 2(n/5)+1 T(n/25) T(n/25) T(n/25) T(n/25) T(n/25) T(n/25) T(n/25) T(n/25) T(n/25) We could keep going... 2(n/5)+1 2n+1 2(n/5)+1 2(n/5)+1 2(n/25)+1 2(n/25)+1 2(1/25)+1 2(n/25)+1 Λ 2(n/25)+1 2(n/25) 1 2(n/25)+1 2(n/25)+1 2(n/25)+1 ЛЛЛ Λ T(n) 4(3) + +3² (2 (1) +1) i-0 =4(3*)+2n Σ() +Σ i=0 = 4(3+) + 2m (*) + (+) =4(*) + () (())+(-1) =4(310)+5n- 5m logs n + 9 = (30g)+5n-5n 3log, n 5log, n 9 = (3log n) + 5n - 5 (3logs") - 1 Blog ")+5n- 1 =5n- (3loga +1) Note that results from this equation will agree with the calculations we did earlier. For example: And: T(5)=5(5)-(35+ +1)=25 -1(3+1 3+1)=23 T(25)=5(25) - (3g 25 + 1) = 125 – +1)=120 While this formula is exact only for n = 5* it gives us a good approximation in other cases: T(17)=5(17) - (17 +1) 8104 As far as time complexity observe that: Thus T(n) O(n). T(n)=n + 1) < 5n And observe that since logs n 5n- (n + 1) = n ≥4n Thus T(n). · O(n) and together we have T(n) A(n)

5. Here is a tree corresponding to T(64) for an unknown recurrence relation: 32+ lg 64 2+lg4 8+ lg 16 2+lg 4 2+lg4 8+ lg 16 2+lg4 7 7 7 7 7 7 7 7 Fill in the details for the corresponding recurrence relation: T(n) = T(1) = T(n/4) + Put scratch work below. Scratch work is not graded but may be used for regrade partial credit. and on the n-values we're analyzing. So as not to go off the deep end, let's consider the example again: Example 3.1. Suppose T(n) = 3T (n/5) + (2n + 1) with T(1) = 4. Let's examine T(n) where n = 5k for some k. To understand why there's a tree involved we can view the total time done as a very small tree, first with one node: T(n) We can expand this according to the recurrence relation, the tree still show- ing the total time: 2n+1 But when does it stop? The tree stops growing when we reach T(1) in the nodes because T(1) = 4 and no more recursion happens. If level i=0 is the top level then as the tree grows we see that level í has entries T(n/5) so the leaf level will happen when we reach T(1) which is when n/5=1 or i = log, n=k. Thus the kth level is the leaf level. Thus in total there are k+1 levels, 0, 1, ..., k, and in those levels: Count Time 2n+1 Level i=0 1 i=1 i=2 3 9 2()+1 2()+1 B i=k-1 i=k 3k-1 3k 4 Level Time 1(2n+1) 3º (2()+1) 3 (2()+1) 31 (2()+1) 9 (2()+1) 32 (2 ()+1) B 2()+13 (2 (5)+1) 3 (4) Thus the total time is the sum of the levels: T(n/5) T(n/5) T(n/5) Of course each of these leaves is its own problem, the tree still showing the total time. 2(n/5)+1 2n+1 2(n/5)+1 2(n/5)+1 T(n/25) T(n/25) T(n/25) T(n/25) T(n/25) T(n/25) T(n/25) T(n/25) T(n/25) We could keep going... 2(n/5)+1 2n+1 2(n/5)+1 2(n/5)+1 2(n/25)+1 2(n/25)+1 2(1/25)+1 2(n/25)+1 Λ 2(n/25)+1 2(n/25) 1 2(n/25)+1 2(n/25)+1 2(n/25)+1 ЛЛЛ Λ T(n) 4(3) + +3² (2 (1) +1) i-0 =4(3*)+2n Σ() +Σ i=0 = 4(3+) + 2m (*) + (+) =4(*) + () (())+(-1) =4(310)+5n- 5m logs n + 9 = (30g)+5n-5n 3log, n 5log, n 9 = (3log n) + 5n - 5 (3logs") - 1 Blog ")+5n- 1 =5n- (3loga +1) Note that results from this equation will agree with the calculations we did earlier. For example: And: T(5)=5(5)-(35+ +1)=25 -1(3+1 3+1)=23 T(25)=5(25) - (3g 25 + 1) = 125 – +1)=120 While this formula is exact only for n = 5* it gives us a good approximation in other cases: T(17)=5(17) - (17 +1) 8104 As far as time complexity observe that: Thus T(n) O(n). T(n)=n + 1) < 5n And observe that since logs n 5n- (n + 1) = n ≥4n Thus T(n). · O(n) and together we have T(n) A(n)

New Perspectives on HTML5, CSS3, and JavaScript
New Perspectives on HTML5, CSS3, and JavaScript
6th Edition
ISBN:9781305503922
Author:Patrick M. Carey
Publisher:Patrick M. Carey
Chapter12: Working With Document Nodes And Style Sheets: Creating A Dynamic Document Outline
Section12.2: Visual Overview: Exploring Attribute Nodes
Problem 4QC
See similar textbooks
icon
Related questions
Question

Top screenshot is question, the rest are examples and explinations.

5. Here is a tree corresponding to T(64) for an unknown recurrence relation: 32+ lg 64 2+lg4 8+ lg 16 2+lg 4 2+lg4 8+ lg 16 2+lg4 7 7 7 7 7 7 7 7 Fill in the details for the corresponding recurrence relation: T(n) = T(1) = T(n/4) + Put scratch work below. Scratch work is not graded but may be used for regrade partial credit. and on the n-values we're analyzing. So as not to go off the deep end, let's consider the example again: Example 3.1. Suppose T(n) = 3T (n/5) + (2n + 1) with T(1) = 4. Let's examine T(n) where n = 5k for some k. To understand why there's a tree involved we can view the total time done as a very small tree, first with one node: T(n) We can expand this according to the recurrence relation, the tree still show- ing the total time: 2n+1 But when does it stop? The tree stops growing when we reach T(1) in the nodes because T(1) = 4 and no more recursion happens. If level i=0 is the top level then as the tree grows we see that level í has entries T(n/5) so the leaf level will happen when we reach T(1) which is when n/5=1 or i = log, n=k. Thus the kth level is the leaf level. Thus in total there are k+1 levels, 0, 1, ..., k, and in those levels: Count Time 2n+1 Level i=0 1 i=1 i=2 3 9 2()+1 2()+1 B i=k-1 i=k 3k-1 3k 4 Level Time 1(2n+1) 3º (2()+1) 3 (2()+1) 31 (2()+1) 9 (2()+1) 32 (2 ()+1) B 2()+13 (2 (5)+1) 3 (4) Thus the total time is the sum of the levels: T(n/5) T(n/5) T(n/5) Of course each of these leaves is its own problem, the tree still showing the total time. 2(n/5)+1 2n+1 2(n/5)+1 2(n/5)+1 T(n/25) T(n/25) T(n/25) T(n/25) T(n/25) T(n/25) T(n/25) T(n/25) T(n/25) We could keep going... 2(n/5)+1 2n+1 2(n/5)+1 2(n/5)+1 2(n/25)+1 2(n/25)+1 2(1/25)+1 2(n/25)+1 Λ 2(n/25)+1 2(n/25) 1 2(n/25)+1 2(n/25)+1 2(n/25)+1 ЛЛЛ Λ T(n) 4(3) + +3² (2 (1) +1) i-0 =4(3*)+2n Σ() +Σ i=0 = 4(3+) + 2m (*) + (+) =4(*) + () (())+(-1) =4(310)+5n- 5m logs n + 9 = (30g)+5n-5n 3log, n 5log, n 9 = (3log n) + 5n - 5 (3logs") - 1 Blog ")+5n- 1 =5n- (3loga +1) Note that results from this equation will agree with the calculations we did earlier. For example: And: T(5)=5(5)-(35+ +1)=25 -1(3+1 3+1)=23 T(25)=5(25) - (3g 25 + 1) = 125 – +1)=120 While this formula is exact only for n = 5* it gives us a good approximation in other cases: T(17)=5(17) - (17 +1) 8104 As far as time complexity observe that: Thus T(n) O(n). T(n)=n + 1) < 5n And observe that since logs n<logan we have 3log," <3¹º3" = n so that for n 1 we have: 1 T(n) 5m ½½(3log + 1) > 5n- (n + 1) = n ≥4n Thus T(n). · O(n) and together we have T(n) A(n)
Transcribed Image Text:5. Here is a tree corresponding to T(64) for an unknown recurrence relation: 32+ lg 64 2+lg4 8+ lg 16 2+lg 4 2+lg4 8+ lg 16 2+lg4 7 7 7 7 7 7 7 7 Fill in the details for the corresponding recurrence relation: T(n) = T(1) = T(n/4) + Put scratch work below. Scratch work is not graded but may be used for regrade partial credit. and on the n-values we're analyzing. So as not to go off the deep end, let's consider the example again: Example 3.1. Suppose T(n) = 3T (n/5) + (2n + 1) with T(1) = 4. Let's examine T(n) where n = 5k for some k. To understand why there's a tree involved we can view the total time done as a very small tree, first with one node: T(n) We can expand this according to the recurrence relation, the tree still show- ing the total time: 2n+1 But when does it stop? The tree stops growing when we reach T(1) in the nodes because T(1) = 4 and no more recursion happens. If level i=0 is the top level then as the tree grows we see that level í has entries T(n/5) so the leaf level will happen when we reach T(1) which is when n/5=1 or i = log, n=k. Thus the kth level is the leaf level. Thus in total there are k+1 levels, 0, 1, ..., k, and in those levels: Count Time 2n+1 Level i=0 1 i=1 i=2 3 9 2()+1 2()+1 B i=k-1 i=k 3k-1 3k 4 Level Time 1(2n+1) 3º (2()+1) 3 (2()+1) 31 (2()+1) 9 (2()+1) 32 (2 ()+1) B 2()+13 (2 (5)+1) 3 (4) Thus the total time is the sum of the levels: T(n/5) T(n/5) T(n/5) Of course each of these leaves is its own problem, the tree still showing the total time. 2(n/5)+1 2n+1 2(n/5)+1 2(n/5)+1 T(n/25) T(n/25) T(n/25) T(n/25) T(n/25) T(n/25) T(n/25) T(n/25) T(n/25) We could keep going... 2(n/5)+1 2n+1 2(n/5)+1 2(n/5)+1 2(n/25)+1 2(n/25)+1 2(1/25)+1 2(n/25)+1 Λ 2(n/25)+1 2(n/25) 1 2(n/25)+1 2(n/25)+1 2(n/25)+1 ЛЛЛ Λ T(n) 4(3) + +3² (2 (1) +1) i-0 =4(3*)+2n Σ() +Σ i=0 = 4(3+) + 2m (*) + (+) =4(*) + () (())+(-1) =4(310)+5n- 5m logs n + 9 = (30g)+5n-5n 3log, n 5log, n 9 = (3log n) + 5n - 5 (3logs") - 1 Blog ")+5n- 1 =5n- (3loga +1) Note that results from this equation will agree with the calculations we did earlier. For example: And: T(5)=5(5)-(35+ +1)=25 -1(3+1 3+1)=23 T(25)=5(25) - (3g 25 + 1) = 125 – +1)=120 While this formula is exact only for n = 5* it gives us a good approximation in other cases: T(17)=5(17) - (17 +1) 8104 As far as time complexity observe that: Thus T(n) O(n). T(n)=n + 1) < 5n And observe that since logs n<logan we have 3log," <3¹º3" = n so that for n 1 we have: 1 T(n) 5m ½½(3log + 1) > 5n- (n + 1) = n ≥4n Thus T(n). · O(n) and together we have T(n) A(n)
Expert Solution
steps

Step by step

Solved in 2 steps with 1 images

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Recommended textbooks for you
New Perspectives on HTML5, CSS3, and JavaScript
New Perspectives on HTML5, CSS3, and JavaScript
Computer Science
ISBN:
9781305503922
Author:
Patrick M. Carey
Publisher:
Cengage Learning
Oracle 12c: SQL
Oracle 12c: SQL
Computer Science
ISBN:
9781305251038
Author:
Joan Casteel
Publisher:
Cengage Learning
C++ Programming: From Problem Analysis to Program…
C++ Programming: From Problem Analysis to Program…
Computer Science
ISBN:
9781337102087
Author:
D. S. Malik
Publisher:
Cengage Learning
Operations Research : Applications and Algorithms
Operations Research : Applications and Algorithms
Computer Science
ISBN:
9780534380588
Author:
Wayne L. Winston
Publisher:
Brooks Cole
Systems Architecture
Systems Architecture
Computer Science
ISBN:
9781305080195
Author:
Stephen D. Burd
Publisher:
Cengage Learning
Programming Logic & Design Comprehensive
Programming Logic & Design Comprehensive
Computer Science
ISBN:
9781337669405
Author:
FARRELL
Publisher:
Cengage
SEE MORE TEXTBOOKS