
Title:
02ps02 Recurrence Relation

Description:

For this problem, we’re going to start off with a

template for a recursively generated graph.

What the template says, if we want one node,

we just return a single node. For other values

make a G1 and a G2 that are half the size and

then we make login connections between G1

and G2 by picking a random point and

connecting it with a random node, another

random node and connecting it with a random

node et cetera and then return. So this has the

recurrence relationship that only have node

with zero edges and if we have N nodes, we

get two times the number of nodes we have

for a graph of half the size plus big data of log

in and so what we want you to do is to solve

this recurrence.

But we’re going to do this one a little differently

than some of our previous homework

assignments. Instead of a multiple choice

question, we want you to explain how to

actually solve this. So below there is a form

link and at that link you’ll see this question

restated. What we want you to do is write up

your answer, post in response to the form, get

the link for your answer and then insert it here.

I’ll give you an example to make this more

clear. So here is the question on the form and

you should write up your answer, some

possible answers might be that T of N is data

login, N login, any other function and then you

should explain why you’ve answered like this.

Or to submit your answer hit the link button,

copy of the link, and there are few copy of the

link pasted into the box here.