I am trying to prove why splitting the sample space in half in each iteration, gives us the best outcome in terms of time complexity, compared to splitting the sample space in other ratios like 1:3, 1:4, etc.
Intuitively, splitting the sample space into half in each iteration will result a better time overall, but I am trying to find a way to prove this mathematically.
I have tried to use the expected value approach, but it seems to be getting me nowhere. Can someone please tell me how to prove this?
So I guess what you want is the average number of steps to find a random element of your sample space. For simplicity I will assume that this element is chosen with equal probability out of the sample space. Writing out all the details perfectly is a bit annoying and hard to read, especially due to all the unavoidable rounding, so here is the basic idea for an $1$:$(n-1)$-split:
Assume you know that your element is in an interval of length k. It does not matter which interval due to the equal probability. If $k=1$ then you finish in this step, so your average number of steps is $1$. If $k>1$, then you choose a pivot element $1/n$th along the way. The probability that the element you look for lies before the pivot is $1/n$, then you continue with an interval of length $k/n$. Otherwise with probability $(n-1)/n$ you continue with an interval of length $(n-1)k/n$. So if $E_k$ is your expected value of steps for an interval of length $k$, you get a recursion of the form
$$ E_k = \begin{cases} 1 & k \leq 1 \\ \frac1n E_{k/n} + \frac{n-1}n E_{(n-1)k/n}+1 & k > 1 \end{cases} $$
only with a lot more rounding. In the boring case $n=2$, you will get $E_k = E_{k/2} +1$, which leads to $E_k = \log_2 k+1$. I don't see the exact formula right now, but you can probably estimate that the general case is worse using induction.