Recursive_3_B

T(n) = 2T(n/2) + n
       T(n)---------n
       /    \
 T(n/2)       T(n/2)-------2(n/2)
   / \          /   \
T(n/4) T(n/4) T(n/4) T(n/4) ------4(n/4)
  / \    ...   ...   ...
...  ...
Now, let's write the expression for the total cost:
LHS
n/2^(k)=1        The depth of the tree is logn base 2.
k=log n base 2
let's calculate the total work done by summing up the work at each level
T(n)=n+n/2+n/4+n/8.......+n/2^k
T(n)=n(1+1/2+1/4+.........1/2 ^logn base 2)
by geometric progression  sum of the series is 1/1-r=2
T(n)=n(2)
time complexity is  O(n)