## ← 02ps-02 Recurrence Relation

• 1 Follower
• 34 Lines

### Get Embed Code 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=I-vokzJP-f8" data-team="udacity"></div> ``` 3 Languages

Showing Revision 2 created 11/07/2012 by podsinprint_user1.

1. For this problem, we’re going to start off with a
2. template for a recursively generated graph.
3. What the template says, if we want one node,
4. we just return a single node. For other values
5. make a G1 and a G2 that are half the size and
6. then we make login connections between G1
7. and G2 by picking a random point and
8. connecting it with a random node, another
9. random node and connecting it with a random
10. node et cetera and then return. So this has the
11. recurrence relationship that only have node
12. with zero edges and if we have N nodes, we
13. get two times the number of nodes we have
14. for a graph of half the size plus big data of log
15. in and so what we want you to do is to solve
16. this recurrence.
17. But we’re going to do this one a little differently
18. than some of our previous homework
19. assignments. Instead of a multiple choice
20. question, we want you to explain how to
21. actually solve this. So below there is a form