Solving the recurrence T (n) = T (n / 2) + Θ (1) by substituting
So, I understand how to do it when the repetition looks something like this:
T (n) = 2T (n / 2) + n
In this case, I would guess the answer would be O (nlogn) and then use induction to prove it. But for this I am thrown out by Θ (1). How would you do it? If you could do the induction steps that would be awesome.
Thank you very much!
source to share