Tip:
Highlight text to annotate it
X
What we're going to do right now is a recurrence relation,
which is a kind of recursive mathematical function,
which is a good match for this recursive algorithmic expression for RecRussian--
RecRussian recurrence relation.
Looking at the structure of RecRussian, if a is 0, then it's going to execute 1 statement--
basically the test to see whether it’s 0 and returns.
Otherwise, if a is bigger than 0 and even, let's take a look at what RecRussian does in that case.
We come in here with a number that is even and greater than 0 is going to execute
the condition of this if statement, which fails so there's 1 of that.
Then 1 more to do this plus it's going to recursively workout the value of this quantity.
Then one more operation to multiply that by 2.
I call a total of 3 plus however long it takes to multiply a over 2 times b.
We don't know what that is.
We're imaging that we're going be able to create a function T
that is going to give us the answer to that.
Let's just leave it at that for now.
Finally, in the case where a is odd, it's going to execute the condition of this if statement,
the condition of this if statement, both of which will fail.
Then it will recursively compute the product, and then basically execute the returns.
A total of 3 statements plus however long it takes to do the recursive call--
so 3 statements plus this particular kind of recursive call.
This now is a mathematical specification of a function.
We don't know at the moment what the relationship is between a and T(a),
but at least it's fully specified.
It turns out that you actually can solve this pretty easily
by using what we already worked out about the number of times
you can divide a number a in half, rounding down if it's odd,
before you get down to 0.
See if you can put that together to try to answer the question
what does T(a) equal from these set of choices.