Recursion relation_3(1)

a. T(n) = 2T(n-1) +1
            T(n)
           /    \
      T(n-1)      T(n-1)
        /  \          /   \
    T(n-2) T(n-2) T(n-2) T(n-2)
      ...   ...   ...   ...
       |     |     |     |

for k times
LEFT SIDE              RIGHT SIDE
n-k=0                   n-k=0
Now, let's calculate the cost at each level:

Level 0: 1T(n)
Level 1: 2T(n-1)
Level 2: 4T(n-2)
Level 3: 8T(n-3)
.
.
.
T(n)+2T(n−1)+4T(n−2)+8T(n−3)+…+2^kT(n−k)
if we sub n-k=1 i.e. k=n-1 we get base case condition
T(n)+2T(n−1)+4T(n−2)+8T(n−3)+…+2^(n-1)T(1)
by geometric progression
T(n)=2^n-T(1)
O(2^n)