How to solve this recurrence relation: T(n) = 2T(n/2) + 1

algorithm, recurrence

Solution

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.

Problem

Original source