i'm trying to proof that quickSelect algorithm RunTime complexity is: Theta(n)
With Akra-Buzzi method.
So i need to Solve this recursive function: T(n) = T(n/5) + T(7n/10) + n
i need to find p, such that: (1/5)^p + (7/10)^p = 1.
and i cant solve this exponential equation :/
Consider that you look for the zero of function $$f(p)=\left(\frac{1}{5}\right)^p+\left(\frac{7}{10}\right)^p-1$$ For simplicity of further notations, let $a=\frac{1}{5}$ and $b=\frac{7}{10}$.
We have $f(0)=1$ and $f(1)=-\frac{1}{10}$; so the solution is a bit smaller than $1$. Just start Newton method with $p_0=1$ and you will have as iterates $$p_{n+1}=p_n-\frac{f(p_n)}{f'(p_n)}=p_n-\frac{a^{p_n}+b^{p_n}-1 }{a^p \log (a)+b^p \log (b) }$$ This would give $$\left( \begin{array}{cc} n & p_n \\ 0 & 1.000000 \\ 1 & 0.825040 \\ 2 & 0.839659 \\ 3 & 0.839780 \end{array} \right)$$