I am having trouble in understanding this example(as the attached the picture below). I basically have 2 questions which these questions are related to each other.
- Is T(N) for N = 1 must equal to 1 for any reccurences case in substitution method by using induction(in basis step)?
- If it is not, then why in the example is equal to 1? Because if I put N = 1 to the >> T(N)=2T(N/2)+N the result is not equal to 1 instead of 2.
Can someone explain? Example of attached picture
