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

1. タイトル：
   01-29 Recurrence Relation
2. 概説：

3. 0 0:00 - 0:02
   What we're going to do right now is a recurrence relation,
4. 2000 0:02 - 0:05
   which is a kind of recursive mathematical function,
5. 5000 0:05 - 0:09
   which is a good match for this recursive algorithmic expression for Rec_Russian--
6. 9000 0:09 - 0:11
   Rec_Russian recurrence relation.
7. 11000 0:11 - 0:16
   Looking at the structure of Rec_Russian, if a is 0, then it's going to execute 1 statement--
8. 16000 0:16 - 0:19
   basically the test to see whether it’s 0 and returns.
9. 19000 0:19 - 0:25
   Otherwise, if a is bigger than 0 and even, let's take a look at what Rec_Russian does in that case.
10. 25000 0:25 - 0:29
    We come in here with a number that is even and greater than 0 is going to execute
11. 29000 0:29 - 0:32
    the condition of this if statement, which fails so there's 1 of that.
12. 32000 0:32 - 0:38
    Then 1 more to do this plus it's going to recursively workout the value of this quantity.
13. 38000 0:38 - 0:41
    Then one more operation to multiply that by 2.
14. 41000 0:41 - 0:48
    I call a total of 3 plus however long it takes to multiply a over 2 times b.
15. 48000 0:48 - 0:50
    We don't know what that is.
16. 50000 0:50 - 0:52
    We're imaging that we're going be able to create a function T
17. 52000 0:52 - 0:54
    that is going to give us the answer to that.
18. 54000 0:54 - 0:56
    Let's just leave it at that for now.
19. 56000 0:56 - 1:01
    Finally, in the case where a is odd, it's going to execute the condition of this if statement,
20. 61000 1:01 - 1:04
    the condition of this if statement, both of which will fail.
21. 64000 1:04 - 1:09
    Then it will recursively compute the product, and then basically execute the returns.
22. 69000 1:09 - 1:13
    A total of 3 statements plus however long it takes to do the recursive call--
23. 73000 1:13 - 1:17
    so 3 statements plus this particular kind of recursive call.
24. 77000 1:17 - 1:20
    This now is a mathematical specification of a function.
25. 80000 1:20 - 1:24
    We don't know at the moment what the relationship is between a and T(a),
26. 84000 1:24 - 1:26
    but at least it's fully specified.
27. 86000 1:26 - 1:29
    It turns out that you actually can solve this pretty easily
28. 89000 1:29 - 1:33
    by using what we already worked out about the number of times
29. 93000 1:33 - 1:36
    you can divide a number a in half, rounding down if it's odd,
30. 96000 1:36 - 1:38
    before you get down to 0.
31. 98000 1:38 - 1:41
    See if you can put that together to try to answer the question
32. 101000 1:41 -
    what does T(a) equal from these set of choices.