Divide and Conquer
Wednesday, May 13, 2015
8:40 AM
<<divideandconquer2.pdf>>
Inserted from: <file://\\psf\Dropbox\Schoolworks\Waterloo\4B\CS431\divideandconquer2.pdf>







So is the guess wrong?
No, but sometimes the math just doesn't work out.



… 


The floor and ceiling goes away since the result is always an integer 




EX: 





This is unintuitive. We make the induction work by lowering the bound. Read 4.3 from text 












Recall Math239 solution of recurrence relations (Homogeneous linear recurrences):



Master Theorem






Created with Microsoft OneNote 2010
One place for all your notes and information