Recursion Tree Method
(To solve recurrence and get time complexity of recursive function)
1)We write non-recursive part as root of tree and recursive part as it's children.
Then take sum of nodes in each level & find Sum of these sums of each level
generally terms of thi new Sum will be in ap,gp etc with number of terms as height of tree.
Note : if recursive part is T(n/2) then height of tree is log(n)
if it's T(n-1) then height is n.
2)We keep on expanding Children untill we reach the base case ( aka leaves ).
T(n) = 2T(n-1) + cn
T(1) = c
Where cn is non recursive part.
Note : instead of 0(1) we write constant c, for 0(n) we write cn
Keep c same everywhere.