:-$ 
Header Image
Creative Commons image courtesy of Flickr user StormPetrel1-
Recent Posts
Recent Comments
- In the Spotlight: MAT2540 – Discrete Structures and Algorithms II – The Open Road on Links
- OpenLab Workshop for Opening Gateways Fellows | 2018-2019 Opening Gateways Faculty Seminar on Final Exam Review
- Eric on Eric’s Final Review
- Kate Poirier on Hints/reminders from today’s class
- Kate Poirier on Final Exam Review
Archives
Categories
Meta
Nice question choice, Heriberto. This one is trickier than it seems, so it helps that you included the example
. You saw that when 
there are 
rounds in the while loop. However, you go on to say that for general 
, there are 
rounds in the while loop (I’m paraphrasing)…but this doesn’t agree with your example where 
. 
, not 
, so your choice of 
isn’t correct. You’re right that something’s going on with base 
since the value of 
doubles every round…but you’ll want to find a function that grows much more slowly than 
does. (Hint: draw a tree and think about today’s class.)
Secondly, the exercise is asking you to count the number of operations (addition or multiplication) performed by the algorithm. It looks like you forgot this part. It’s probably easiest to count the number of OPERATIONS PER ROUND in the while loop and then use the answer above to determine the NUMBER OF ROUNDS in the while loop. Then you can multiply these two values to get a formula for the total number of operations.