Tip:
Highlight text to annotate it
X
All right. How do we work out the answer to this?
Well, the number of times that it gets divided in half before it reaches 0
is this expression--log base 2 of a plus 1.
But notice what's happening.
Each time that we divide it in half, we're actually adding 3 to the pile.
This is not quite right.
We actually need to do 3 times this, which is like this,
but then when we get to the bottom, there's going to be 1 more added into the sum.
This is the answer.
In this particular instance, we got kind of lucky that we happened to have
a recurrence relation that we could analyze using one of the formulas that we already worked out.
One of the things we're going to do next time is look at these kinds of relationships more generally.
How do we take a recurrence relation and turn it into a concrete formula without getting
bogged down in all of the details.
One of the things we're going to try to do is ignore some of these pesky constants
like the 3s and the 4s and so forth,
so we can take a function like T(a) and say, well,
it kind of grows in a log-like manner and not really get too worried about the details.