Proving time-complexity analysis for merge-sort-like algorihtm

Question

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:

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!

Answer 1

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). $$