Tip:
Highlight text to annotate it
X
Let's go back and take a look at this again.
We now know how deep. It's log n.
And we know how many leaves. It's n.
At each of these levels, not only is it going to compute the subgraph of the given size,
but then it's going to add 1 more edge that is the connector between the 2 components.
So there's 1 of those edges gets added at this level.
There's 2 that get added at this level.
There's 4 that get added at this level.
There's 8 that get added at this level.
Until finally, at the end of the day, there's zero that get added at this level.
But the level right above it, there's n.
So the total number of edges that get added is the sum of all these things--
n + n/2 + n/4 to 1.
That is basically 2n--so that we don't have to say basically
we can say it's exactly Θ(n),
meaning it's basically 2n.
What we basically rediscovered is that the number of edges in a tree,
or one of these randomly generated trees,
is still linear.
That's not so surprising, but this particular way of doing the analysis with this tree
is going to turn out to be useful in some other settings.