Recurrences and Big-O Notation in Data Structures and Algorithms
Dive into the concepts of recurrences and Big-O notation in CSE 373: Data Structures and Algorithms lecture 8. Learn about the methods for analyzing running time of algorithms, handling late submissions for projects, and mastering the unrolling technique. Practice writing recurrences and analyzing code for better understanding.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Lecture 8:Tree Method CSE 373: Data Structures and Algorithms
Administrivia Project 1 Part 1 due tonight - Fill out the late day form on the project page if you need to use late days. Project 1 Part 2 out tonight - Fix bugs from part 1 to get half of your missed points back. - Run experiments on your code (connect the programming project to things learned in lecture). Exercise 1 due Friday
Dont Panic We couldn t apply Master Theorem to this recurrence: ? ? = ? ? 1 + 1 if ? > 1 3 otherwise The books don t have a nice theorem; They do have methods for figuring out the big-O.
Unrolling Idea: keep plugging the definition of ?() into itself. Until you find the pattern and can hit the base case. ? ? = ? ? 1 + 1 if ? > 1 3 otherwise
Unrolling ? ? = ? ? 1 + 1 if ? > 1 3 otherwise ? ? 1 + 1 [? ? 1 1 + 1] + 1 = ? ? 2 + 1 + 1 ? ? 2 1 + 1 + 1 + 1 = ? ? 3 + 1 + 1 + 1 ? ? 3 1 + 1 + 1 + 1 + 1 = ? ? 4 + 1 + 1 + 1 + 1 ? ? ? + ? for any ?. The thing we don t understand is ?(). We can get rid of it by hitting the base case. Set ? so that ? ? = 1. ? = ? 1 ? ? ? 1 + ? 1 ? 1 + ? 1 = 3 + ? 1 = ? + 2 ? ? = ? ? = ? + 2
We did it! For BSTs: If we re in the case where everything is balanced, we have a much better dictionary. But if have that degenerate BST, we re no better off than with an array or linked list. For analyzing code: We didn t just get the big- , we actually got an exact expression too! Let s try another one!
More Practice Write a recurrence to describe the running time of this function, then find the big- for the running time. public int dumbFindMax(int[] arr, int hi){ if(hi == 0) return arr[0]; int maxInd = 0; for(int i=0; i<hi; i++){ if(arr[i] > arr[maxInd]) maxInd=i; } return Math.max(arr[maxInd], dumbFindMax(arr, hi-1)); }
? ? = ? ? 1 + ? if ? 2 1 otherwise You probably had some lower-order terms when you wrote this recurrence. When we re solving recurrences we usually ignore lower-order terms in non-recursive work. They make the algebra a lot more complicated, and don t affect the big-O. We ll tell you to ignore lower-order terms when we want you to.
? ? = ? ? 1 + ? if ? 2 1 otherwise ? ? 1 + ? ? ? 1 1 + ? 1 + ? = T n 2 + n 1 + n ? ? 3 + ? 2 + ? 1 + ? ? ? 4 + ? 3 + ? 2 + ? 1 + ? ? 1 ? ? ? + ? ? ?=0 Plug in ? so ? ? is 1 ? 1 1 ? ? (? 1) + ? ? = ?=0
? ? = ? ? 1 + ? if ? 2 1 otherwise ? 2 ? 2 ? 2 1 + ? ? = 1 + ? ? ?=0 ?=0 ?=0 ? 2 = 1 + ? ? 1 ? ?=0 ? 1 ? 2 2 2+3? = 1 + ? ? 1 = ?2 ? ?2 (?2) 2 1
? 4+ ?2 if ? > 1 otherwise ? ? = 3? 4 We can unroll to get the answer here, but it s really easy to make a small algebra mistake. If that happens we might not be able to find the pattern -Or worse find the wrong pattern. There s a way to organize our algebra so it s easier to find the pattern.
Tree Method Idea: We ll do the same algebra, but let s give ourselves a visual to make the organization easier. We ll make a tree. Each node of the tree represents one recursive call - The children of that node are the new recursive calls made tree.
Tree Method Practice 4 ? ?? ? 1 ? 4 ? ? = + ?2 ?? ?????? 3? ? 4 ? 4 ? ? n2 ? 4 + ?2 ? + ? + ? Answer the following questions: 1. What is the size of the input on level ?? 2. What is the work done by each node on the ?? recursive level 3. What is the number of nodes at level ?? 4. What is the total work done at the i^th recursive level? 5. What value of ? does the last level occur? 6. What is the total work across the base case level? 2 ? 4 n 2 2 ? 16 ? 16 ? 16 ? 4 ? 16 ? 16 ? ? 16 ? 4 ? 2 2 2 + ? n 4 n 4 ? 4 ? 16 ? 16 ? 16 4 ? 4 ? ? + ? + ? + ? + ? 4 + ? + ? + ? + ? ? 16 ? 16 ? 16 ? 16 ? 16 16 ? 16 16 ? 16 ? 16 16 ? 16 2 2 2 ? 16 2 2 2 ? 16 ? 16 2 ? 16 ? ? 2 2 ? 16 ? ? 16 ? ? ? ? ? ? ? ? ? 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 EXAMPLE MODIFIED FROM PROVIDED BY CS 161 JESSICA SU HTTPS://WEB.STANFORD.EDU/CLASS/ARCHIVE/CS/CS161/CS161.1168/LECTURE3.PDF 14
5 Minutes Tree Method Practice 4 ? ?? ? 1 ? 4 ? ? = + ?2 ?? ?????? 3? Number of Number of Nodes Nodes 1 Work per Work per Node Node Work per Work per Level Level Level ( Level (i i) ) ? 4? 1. What is the size of the input on level ?? 0 ?2 ?2 2 3 42?2 32 44?2 ? 4 ? 42 1 3 2 ? 4? 2. What is the work done by each node on the ?? recursive level? 2 2 9 3. What is the number of nodes at level ?? base 4 3? 3log4? 4 3log4? 4. What is the total work done at the ?threcursive level? 3? Combining it all together ? 2 ? 4? 3 ?2 = 16 log4? 1 ? 3 5. What value of ? does the last level occur? ?2+ 4?log43 ? ? = 16 ?=0 ? 4?= 1 ? = 4? ? = log4? 6. What is the total work across the base case level? 3log4? 4 power of a log ?log??= ?log?? 4 ?log43 CSE 373 SP 18 - KASEY CHAMPION 15
Tree Method Practice factoring out a constant log4? 1 log4? 1 ? ? 3 3 ? ? = ?2 + 4?log43 ?2+ 4?log43 ? ? = ? ? 16 16 ?=0 ?=0 ??(?) =? ?(?) ?=? ?=? Closed form: Identities are on the webpage. You don t need to memorize them. finite geometric series log4? 3 1 ? 1 16 ??=?? 1 ? 1 ? ? = ?2 + 4?log43 3 16 1 ?=0 So what s the big- ? ? = ?2 16 16 13 log4? ?log43 ? ? = ?2 16 3 16 13 ?2+ 4?log43 16+ ?2+ 4?log43 + 13 13 16 ? ? (?2) CSE 373 SP 18 - KASEY CHAMPION 16
More Tree Method ? 2 ? ? = 6? + 2? if ? > 8 3 otherwise
? 2 Tree Method Practice ? ? = 6? + 2? if ? > 8 3 otherwise Answer the following questions: 1. What is the size of the input on level ?? 2. What is the work done by each node on the ?? recursive level 3. What is the number of nodes at level ?? 4. What is the total work done at the i^th recursive level? 5. What value of ? does the last level occur? 6. What is the total work across the base case level?
5 Minutes ? 2 Tree Method Practice ? ? = 6? + 2? if ? > 2 3 otherwise Number of Number of Nodes Nodes 1 Work per Work per Node Node Work per Work per Level Level Level ( Level (i i) ) ? 2? 1. What is the size of the input on level ?? 0 2? 2? 2? 8 ? 2 2? 1 2 2. What is the work done by each node on the ?? recursive level? 2? ? 82 ? 8 2 4 2 3. What is the number of nodes at level ?? 6? 3 2?1/3 base 3 2log8? 1 4. What is the total work done at the ?threcursive level? 6?2? Combining it all together 2?= 2 3? ? log2(?) 2 2 3?? +1 5. What value of ? does the last level occur? 2?log26 ? ? = ?=0 ? 2?= 2 ? = 2?+1 ? = log2(?) 1 6. What is the total work across the base case level? 6log2(?) 1 3 power of a log ?log??= ?log?? 3 6log2? 6 =1 2 ?log26=1 2 ?log26 CSE 373 SP 18 - KASEY CHAMPION 19
log2(?) 2 2 3?? +1 2?log26 ? ? = ?=0 log2(?) 2 3?+1 finite geometric series 2?log26 = 2? ? 1 ?=0 ??=?? 1 ? 1 = 2?3log2? 1 +1 2?log26 3 1 ?=0 = ? ?log23 +1 power of a log ?log??= ?log?? 2?log26 3 =?log23 +1 +1 2?log26 3 =?log26 +1 2?log26=5 1 = log22 6?log26 3 loga? + log?? = log?(??)
