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

Question 1

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.

Question 2

A good explanation of such relations is given in Cormen et al `Introduction to algoithms'. Master Theorem 4.1 in that book treats all recurrent relations of the form T(n) = aT(n/b) + f(n). for various combinations of f, a, and b. One of the cases in that theorem, case 2. can be applied to your example, giving the O(n) estimate. So, to answer your question, you cannot just solve such a relation in the sense of performing some routine computations to end up with a asymptotic, rather you observe that your situation belongs to a class of relations for which an estimate exists.

Question 3

This type of recursions are solved using Master theorem.

In your case a = 2, b = 2 and f(n) = 1. So c = log2(2) = 1 and O(n^1) > O(1), which means that we fall in the third case and therefore a complexity is O(n).