## ← 01-29 Recurrence Relation

• 1 フォロワー
• 30 Lines

### 埋め込みコードを取得する x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=l23fMA3qBpY" data-team="udacity"></div> ``` 2言語

• 英語(米国) [en]
• 日本語 [ja]

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.