How do I draw a recursion tree for T(n) = 4T(n-1) 2. with n>1 and T(1) = 2. usually there is n in the end, but in this case there is none.

CodePudding user response：

The given recurrence relation has a constant term, which leads to a very trivial recursion tree:

      _______________2______________
     /          /        \          \
  __2__      __2__      __2__      __2__    
 / | | \    / | | \    / | | \    / | | \
2  2 2  2  2  2 2  2  2  2 2  2  2  2 2  2
...        ...        ...        ...

The number of levels of the tree is dermined by the recurrence term: