# 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!

+3

source to share

1 answer