Discussion 7: Asymptotic Analysis Christine Zhou Agenda Announcements Recursive Runtime Worksheet Announcements Remember to commit frequently! HW4 was due yesterday Proj1 is due this Friday! Extra OH on Wednesday 6-8PM, Thursday 7-9PM, most likely in the labs! Extra credit opportunity: Mid-semester survey! Keep your eyes peeled Advising Sessions: tinyurl.com/cs61b-advising CS 370 Signups! Discussion survey: tinyurl.com/disc7cz 1 More Running Time Practice Problem public void hello(int n) { if (n == 0) { return; } else { for (int i = 0; i < 10000000; i += 1) { System.out.println(“hello”); } hello(n-1); } } Let’s draw the “work done” tree! 2 Recursive Running Time There are some typos on the discussion sheet, sorry!! public void andslam(int N) { if (N > 0) { for (int i = 0; i < N; i += 1) { System.out.println(“bigballer.jpg”); } andslam(N/2); } } 2 Recursive Running Time 2 Recursive Running Time 3 Hey you watchu gon do? a) Algorithm 1 b) Neither c) Neither d) Algorithm 2 e) Neither Big Ballin’ Bounds Big Theta Big O Big Omega 4 Big Ballin’ Bounds