Recurrences

Recurrences:

Next topic came in the course, which includes finding Time Complexity of recursive algorithms.

where we define the exact number of steps for base cases and a recurrence relation in terms of T(n) based on the algorithm for arbitrary values of  n > b, where b is a natural number.

This looked fairly simple until we got into proving upper and lower bounds of Recursive binary search

and merge sort algorithm,   To get the idea of bound for a certain Algorithm we basically unwind the recurrence based on its definition.  Normally Recursive algorithms involve Divide and conquer technique to define a recurrence, where we Split the input in two or more halves. So, then after unwinding the recurrence, we end up getting a closed form our recurrence relation.

That closed form tells us the exact bound for our algorithm.

Then we set out to prove Big O and Big Omega that bound for our recursive Algorithm.

The Proof Of Big Omega for recursive Binary search is straight forward, 

But Big O is difficult if your trying to prove it all by yourselves, it involves one trick which is not obvious and cannot be thought of easily,   Even Great researchers came to know it through trial and error.

So, I looked in to course notes, Theory of computation book, Google searches you tube videos

to understand the Big O notation for recursive binary search

and talk about Big O and Big Omega for merge sort algorithm, which both involve similar kind of trick in opposite direction.