1
$\begingroup$

Merge sort always divides array of size $n$ into parts each of size $n/2$. It then merges these two parts. So its recurrence relation is $T(n)=2T(n/2) + O(n)$. What if there is an algorithm which is guaranteed to partition the array into two parts of sizes $n/100$ and $99n/100$? So its recurrence relation will be $T(n)=T(n/100)+T(99n/100)+O(n)$.

It feels like this relation is not as good as merge sort in terms of time. I think that such an algorithm's worst case time complexity should be between that of $O(n^2)$ and $O(n\log n)$.

I have two questions:

  1. Is $n/2$ and $n/2$ partitioning the most optimal or $n/100$ and $99n/100$ partitioning also asymptotically optimal?
  2. How to solve the recurrence relation $T(n)=T(n/100)+T(99n/100)+O(n)$?
$\endgroup$
  • $\begingroup$ Have you tried replacing $O(n)$ with $cn$ and unrolling the recurrence a few levels to see what happens? $\endgroup$ – Tassle Sep 12 '20 at 7:59
  • $\begingroup$ Yes I did. After second substitution I got T(n)=T(n/100^3)+3T(99n/100^3)+3T(99^2n/100^3)+T(99^3n/100^3)+ n/100^2 + 99*101n/100^2 +n + n. I can't find any pattern in that. $\endgroup$ – Ayush Sep 12 '20 at 8:22
1
$\begingroup$

The simplest way to answer this question is using the Akra–Bazzi theorem, a vast generalization of the Master theorem. Using the Akra–Bazzi theorem, you can show that the solution of the recurrence $T(n) = T(\alpha n) + T((1-\alpha) n) + O(n)$ is $T(n) = \Theta(n\log n)$ for all constant $\alpha \in (0,1)$.

You can also use a recursion tree. This is a tree in which the root is $n$, and any node whose value is $m \geq n_0$ has two children labeled $\alpha m$ and $(1-\alpha) m$. The total cost of the algorithm is proportional to the sum of all values in the tree.

Suppose that $n$ is very large, and consider the first few levels of the tree:

  • The first level consists of the root, labeled $n$.
  • The second level consists of two nodes, labeled $\alpha n$ and $(1-\alpha) n$.
  • The third level consists of four nodes, labeled $\alpha^2 n$, $\alpha(1-\alpha) n$, $\alpha(1-\alpha) n$, and $(1-\alpha)^2 n$.

You can see that the labels in each level sum to $n$. At some point this will stop happening because the tree has leaves when the value drops below $n_0$, but the first $\min(\log_{1/\alpha} (n/n_0), \log_{1/(1-\alpha)} (n/n_0))$ are complete. In contrast, each level sums up to at most $n$, and there are at most $\max(\log_{1/\alpha} (n/n_0), \log_{1/(1-\alpha)} (n/n_0))$ levels. Putting the two together, we see that the complexity is $\Theta(n\log n)$.


With more effort we can find the dependence of the complexity on $\alpha$. For concreteness, let us assume that the recurrence is $T(n) = T(\alpha n) + T((1-\alpha) n) + n$, and consider $S(n) = T(n)/n\log n$, which satisfies the recurrence $$ S(n) = \frac{\alpha n \log (\alpha n)}{n \log n} S(\alpha n) + \frac{(1-\alpha) n \log ((1-\alpha) n)}{n \log n} S((1-\alpha) n) + \frac{1}{\log n}. $$ Suppose that $S(n) \longrightarrow C$. Substituting $S(n) = C$ in the recurrence, we obtain \begin{align} C &= \frac{\alpha n \log (\alpha n)}{n \log n} C + \frac{(1-\alpha) n \log ((1-\alpha) n)}{n \log n} C + \frac{1}{\log n} \\ &= \alpha C + (1-\alpha) C + \frac{\alpha \log \alpha C + (1-\alpha) \log (1-\alpha) C + 1}{\log n} \\ &= C + \frac{1 - h(\alpha) C}{\log n}, \end{align} where $h(\alpha)$ is the entropy function. Thus, if $S(n) \longrightarrow C$ then $C = 1/h(\alpha)$, which is indeed minimized when $\alpha = 1/2$ and symmetric with respect to $\alpha$ and $1-\alpha$.

Here is another way to see where $h(\alpha)$ is coming from. Consider a random element from the original array. With probability $\alpha$, it belongs to the first half of size $\alpha n$, and with probability $(1-\alpha)$ it belongs to the second half of size $(1-\alpha) n$. In this way, we can trace what happens to the element until it reaches a subarray of size $n_0$ or less. The contribution of this element to the total complexity is the depth at which the terminal subarray is reached, so we are interested in the expected depth of this process.

Let $N_t$ be the size of the subarray at time $t$. Thus $N_0 = n$, and if $N_t \geq n_0$, then $N_{t+1} = \alpha N_t$ with probability $\alpha$, and $N_{t+1} = (1-\alpha) N_t$ with probability $(1-\alpha)$. It is easy to check that $\mathbb{E}[\log (N_t/N_{t+1}))] = h(\alpha)$. Since $\log(N_t/N_0) = \sum_{s=0}^{t-1} \log(N_{s-1}/N_s)$, linearity of expectation shows that $\mathbb{E}[\log (N_t/n_0)] = t h(\alpha)$ (assuming the the process continues forever, even after reaching size $n_0$), and so the expected time to hit a leaf is $\log(n/n_0)/h(\alpha)$.

$\endgroup$
  • $\begingroup$ In "min(log1/α(n/n0),log1/(1−α)(n/n0))" why are you taking minimum rather than maximum? You are finding that level upto which tree is complete and multpilying this with n. But below this level, there will be some nodes, isn't it? To find the worst case running time why are you not taking maximum depth of tree and then multiply it with n? $\endgroup$ – Ayush Sep 12 '20 at 9:32
  • 1
    $\begingroup$ Right, the second min should have been max. $\endgroup$ – Yuval Filmus Sep 12 '20 at 9:33
  • $\begingroup$ And in Θ(nlogn) the base of log is 100/99, right? if α would have been 2 as it is in merge sort then the complexity would be Θ(nlog2n). Since log2n is lesser than log100/99n so can i say that the above mentioned algorithm is asymtotically slower than merge sort? $\endgroup$ – Ayush Sep 12 '20 at 9:51
  • 1
    $\begingroup$ Big O notation hides constant factors, so $\Theta(n\log n)$ is the same class of functions, no matter what base is used for the logarithm. $\endgroup$ – Yuval Filmus Sep 12 '20 at 12:16

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.