I couldn't find a good answer to how this formula was derived for the divide and conquer algorithm in a 1D Peak-Finding problem.
About the problem
Basically, there's an array of numbers and we want to find a peak in this array (a peak is a number higher than the two numbers to the left and right of it).
$T(n) = T(n/2) + \Theta(1)$
I watched the MIT video on "1. Algorithmic Thinking, Peak Finding" but the formula was just written as though it was something really obvious. I guess it might be, anyone kind enough to explain it?
I can sort of guess that $n/2$ comes from the fact that we are always choosing only one side of the array, but this is really just a guess and I get totally lost when suddenly the formula is expanded and we get