Header ImageCreative Commons image courtesy of Flickr user StormPetrel1
- 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
Test #1 Review 3.3#4
This entry was posted in Test #1 Review. Bookmark the permalink.
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.