Generalized MergeSort time complexity functional equation: $f(n)=2f\left(\frac{n}{2}\right)+cn$

Question

There is a well-known solution to MergeSort time complexity problem. It reduces to solving the following functional equation: $$f(n)=2f\left(\frac{n}{2}\right)+cn$$ It isn't that difficult to solve it for natural input $n$. How to solve it for any real input $x$?

WolframAlpha gives $\frac{cx\log(x)}{\log(2)}+\frac{c_1x}{2}$, where $c_1$ is an arbitrary constant.

Answer 1

Let $n=2^p$ and $g(p)=f(n)$ then $g(p)=2g(p-1)+c2^p$

Homogeneous solution is $g_h(p)=2^pg_h(0)$

Since $2^p$ appear also in RHS then the specific solution is of the form $g_s(p)=(ap+b)2^p$. We can ignore the $b$ since already part of the homogeneous solution, and solving it gives $a=c$.

Therefore calling $c_1=g_h(0)$ we get $$g(p)=g_h(p)+g_s(p)=c_1\,2^p+cp\,2^p$$

Expressed in $n$ this gives $p=\log_2(n)$ and (you can ignore the $\frac 12$ it is absorbed by $c_1$):

$$f(n)=c_1n+cn\,\log_2(n)$$

---

We can do the same for $\frac 1n=2^{-p}$ and $h(p)=f(\frac 1n)$ then $h(p)=2h(p+1)+c2^{-p}$

Which solves similarly to $$h(p)=\frac{c_1}{2^p}-\frac{cp}{2^p}$$

Expressed in $n$ this gives:

$$f(\tfrac 1n)=\frac{c_1}n-\frac cn\,\log_2(n)=c_1\tfrac 1n+c\tfrac 1n\,\log_2(\tfrac 1n)$$

---

Now we would like to show the same formula for the rationals $n=\frac{n_1}{n_2}$ and use continuity of $f$ to prove the expression holds on the reals by density of $\mathbb Q^+$ in $\mathbb R^+$.

Note: continuity of $f$ is not given in the problem, but generally implicitly assumed in functional equations, because without it we just got very weird solutions (multi-branching families of functions).

Unfortunately here we do not really have a mean to express $f(\frac{n1}{n2})$ in function of $f(n_1)$ and $f(\frac 1{n_2})$ and combine them.

BUT there exists another path, in fact the set of binary numbers $\Big\{\frac n{2^m}\mid (n,m)\in\mathbb N^2\Big\}$ is also dense in $\mathbb R^+$.

And we now have a way to progress, the mechanism is exactly the same as before when solving for $h$ since $f(\tfrac{n}{2^m})=2f(\frac n{2^{m+1}})+c\tfrac{n}{2^m}$.

I skip directly to the result which you probably have guessed is:

$$f(\tfrac n{2^m})=c_1\tfrac{n}{2^m}+c\tfrac {n}{2^m}\,\log_2(\tfrac{n}{2^m})$$

We can now conclude by continuity that $$f(x)=c_1x+cx\log_2(x)\text{ for }x\in\mathbb R^+$$

Answer 2

As

$$ f\left(2^{\log_2 q}\right)=2f\left(2^{\log_2 q-1}\right)+cq $$

here $q=\frac nm$ represents any rational. Making now $F(\cdot) = f\left(2^{(\cdot)}\right)$ and $z=\log_2 q$ we follow with

$$ F(z)=2F(z-1)+c 2^z $$

This recurrence has as solution

$$ F(z) = c_0 2^z+c z 2^z $$

and now going backwards with $z = \log_2 q$ we get

$$ f(q) = c_0 q + c q\log_2 q $$