how do we have 2^(n-1) nodes on the last i.e nth level of a recursion tree?
Time complexity in fibb series
Draw the tree structure and you will understand. Level 1 contains only 1 node(ie. 2^0). Level 2 contains 2 node (ie. 2^1). Level 3 contains 8 nodes (ie. 2^3) and so on…
You can therefore generalize that the nth level will have 2^(n-1) nodes.