How many times can you divide a list of n elements in 1/2 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.
You haven't explained what "divide in half" means, but let's assume that it means to divide the list into two halves of as equal size as possible (equal if the number of elements is even, almost equal if it's odd).

You can draw recursive "division in half" as a tree. The root is labelled by the original number of vertices, $n$. A node labelled $1$ is a leaf. Any other node labelled $m &gt; 2$ has two children labelled $\lfloor m/2 \rfloor$ and $\lceil m/2 \rceil$ (this is the "division in half"). As yemelitc shows in their answer, the number of leaves is $n-1$; this is irrespective of the division being "in half". On the other hand, the depth of the tree (number of edges in longest path from root to leaf) is $\lceil \log_2 n \rceil$. You can try to prove this in the case where $n = 2^k$ (you can use induction on $k$).