Test #1 Review 3.3#4

:-$ 20160306_234055_HDR 1457325753882459656418

This entry was posted in Test #1 Review. Bookmark the permalink.

1 Response to Test #1 Review 3.3#4

  1. Kate Poirier says:

    Nice question choice, Heriberto. This one is trickier than it seems, so it helps that you included the example n=10. You saw that when n=10 there are 4 rounds in the while loop. However, you go on to say that for general n, there are 2^n rounds in the while loop (I’m paraphrasing)…but this doesn’t agree with your example where n=10. 2^{10} = 1024, not 4, so your choice of 2^n isn’t correct. You’re right that something’s going on with base 2 since the value of i doubles every round…but you’ll want to find a function that grows much more slowly than 2^n 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.

Leave a Reply

Your email address will not be published. Required fields are marked *