[Solved]: How many times can you divide a list of n elements in 1/2

Problem Detail: 

I am trying to wrap my head around recursion and divide and conquer algorithms. Can someone provide a proof and explanation of how many times a list of n elements can be divided in 1/2 on both sides.. In other words the total number of half divisions in a recursive divide procedure on a list of size n.

Asked By : Brian Vanover

Answered By : yemelitc

Lets assume that the base case in the recursive division procedure is a list of only 1 element.

You mentioned that division is done on both sides. So it turns out that there is no need to think in terms of recursive division. This is because no matter what the procedure is, you end up sub-dividing until there is only 1 element.

So a similar question will be: how many times can we divide a list of n elements into its single elements? Well we do this every day, and we do this n-1 times!

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22656