2
$\begingroup$

I have this algorithm, which is exactly like merge-sort, but instead of halving the array each recursion, it actually splits it into $1/4$ and $3/4$ parts. Other then that, it does exactly the same operation as merge-sort.

The thing is, I can't understand the exact way to calculate a closed form solution to my recursive formula, which I think is: $$T(n) = T(\frac{1}{4}n) + T(\frac{3}{4}n) + O(n)$$

I've gone through the proof of the standard merge-sort implementation recursion closed-form formula (as seen in a khan academy article) and have noticed that as a way to develop intuition on how the recursive formula acts, a binary tree has been drawn. So I decided to try it for myself and the recursion formula I'm trying to prove. What I got was something like the following:

enter image description here

Where $(\frac{3}{4})^Hn$ is the height of the tree.

Because the tree is not complete, I'm confused on how I should calculate that $H$ value (the height of the tree), so I could use it in my worst-case merge-sort-like algorithm analysis. The confusion, in my estimation, lies in my low confidence with $log$ operations. Just can't seem to wrap my head around them. How do I start writing an induction proof for a closed form formula, and how do I even come up with one?

Help is as always, greatly appreciated. Moreover, if there is a source of further learning and something worthwhile reading that might help in this subject, please write that down for me so I could explore by myself. Thanks!

$\endgroup$
1
$\begingroup$

There is no reason to calculate a closed form solution to this recurrence. Indeed, this is not even possible, due to the following reason:

  • $O(n)$ is not a closed form function. It just signifies that the recurrence holds with $O(n)$ replaced by some function $f(n)$ which belongs to the class $O(n)$.

  • It is not clear what happens when you plug in $n$ which is not divisible by 4.

  • A related issue is that there are no initial conditions - the recurrence seemingly never bottoms out.

Any reasonable way to address the latter two concerns will lead to a recurrence which is amenable to the Akra–Bazzi method. According to this method, we first need to calculate the value of $p$ satisfying $$ (1/4)^p + (3/4)^p = 1. $$ The solution to this equation is $p = 1$. The asymptotic solution is then $$ T(n) = O\left(n\left(1 + \int_1^n \frac{O(u)}{u^2} \, du \right)\right) = O(n\log n). $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.