English 字幕

← 01-29 Recurrence Relation


Showing Revision 1 created 06/27/2012 by Amara Bot.

  1. What we're going to do right now is a recurrence relation,
  2. which is a kind of recursive mathematical function,
  3. which is a good match for this recursive algorithmic expression for Rec_Russian--
  4. Rec_Russian recurrence relation.
  5. Looking at the structure of Rec_Russian, if a is 0, then it's going to execute 1 statement--
  6. basically the test to see whether it’s 0 and returns.
  7. Otherwise, if a is bigger than 0 and even, let's take a look at what Rec_Russian does in that case.
  8. We come in here with a number that is even and greater than 0 is going to execute
  9. the condition of this if statement, which fails so there's 1 of that.
  10. Then 1 more to do this plus it's going to recursively workout the value of this quantity.
  11. Then one more operation to multiply that by 2.
  12. I call a total of 3 plus however long it takes to multiply a over 2 times b.
  13. We don't know what that is.
  14. We're imaging that we're going be able to create a function T
  15. that is going to give us the answer to that.
  16. Let's just leave it at that for now.
  17. Finally, in the case where a is odd, it's going to execute the condition of this if statement,
  18. the condition of this if statement, both of which will fail.
  19. Then it will recursively compute the product, and then basically execute the returns.
  20. A total of 3 statements plus however long it takes to do the recursive call--
  21. so 3 statements plus this particular kind of recursive call.
  22. This now is a mathematical specification of a function.
  23. We don't know at the moment what the relationship is between a and T(a),
  24. but at least it's fully specified.
  25. It turns out that you actually can solve this pretty easily
  26. by using what we already worked out about the number of times
  27. you can divide a number a in half, rounding down if it's odd,
  28. before you get down to 0.
  29. See if you can put that together to try to answer the question
  30. what does T(a) equal from these set of choices.