Let's assume for simplicity that n
is a power of 2. For example, if n = 8
and the base case T(0) = 0
then the tree of recursive call looks like that:
1 n = 8, depth 0
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
1 1 n = 4, depth 1
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
1 1 1 1 n = 2, depth 2
/ \ / \ / \ / \
/ \ / \ / \ / \
1 1 1 1 1 1 1 1 n = 1, depth 3
/ \ / \ / \ / \ / \ / \ / \ / \
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 n = 0, depth 4
The tree has log(n) + 1
levels not counting the lowest level, because each node in this level has cost 0
. In order to calculate T(n)
, in this case T(8)
, you have to sum up all ones in the tree.
Notice that on the depth i
there are 2^i
nodes, each with cost equal 1
.
So the formula for a sum of ones in the tree is:
sum [from i = 0 to log(n)] 2^i
this is a geometric series with a_1 = 1
and q = 2
, and you want to know the sum of first log(n) + 1
values. This is given by the formula:
(1 - 2^(log(n) + 1)) / (1 - 2) = 2n - 1
So for n = 8
, the result is 15
.
I hope this helps you.