I been recently trying to teach my self algorithms from MIT Open-Course Ware. I was learning Divide and Conquer technique on a 1D array, to find a peak.
I understand the worst case complexity is O(log n), essentially how many times can you split the array in half.
I also understand the best case complexity is Omega(n), find a peak at n/2.
Two things i didn't understand was why is the complexity theta(log n) as well.
Also the lecturer said the work needed for this algorithm is as follows:
T(n) = T(n/2) + Θ(1) = Θ(1) + . . . + Θ(1) (log2(n) times) = Θ(log2(n))
can any explain these two problems for me. Many thanks.