Cheap and Secure Web Hosting Provider : See Now

[Answers] Asymptotic Runtime of Interrelated Functions

, , No Comments
Problem Detail: 

I have two functions $S$ and $T$ which are interrelated and I want to find the asymptotic worst case runtime. The fact that they are interrelated is stumping me...

How would I find the asymptotic runtime $S(n)$ and $T(n)$?

$$ \begin{align*} S(n) &= 2S(n/4) + T(n/4) \\ T(n) &= S(n/2) + 2T(n/2) \end{align*} $$

Asked By : recursion.ninja

Answered By : Yuval Filmus

You can expand the definition of $T(n)$ as follows: $$ \begin{align*} T(n) &= S(n/2) + 2T(n/2) \\ &= S(n/2) + 2S(n/4) + 4T(n/4) \\ &= S(n/2) + 2S(n/4) + 4S(n/8) + 8T(n/8) \\ &= \dots \\ &= S(n/2) + 2S(n/4) + 4S(n/8) + \dots. \end{align*} $$ Substituting this in the definition of $S(n)$, we get $$ S(n) = 2S(n/4) + S(n/8) + 2S(n/16) + 4S(n/32) + \dots. $$ Let's try to estimate the value of $S(n)$. Guessing $S(n) = n^\alpha$ and eliminating the common term $n^\alpha$, we get $$ \begin{align*} 1 &= \frac{2}{4^\alpha} + \frac{1}{8^\alpha} + \frac{2}{16^\alpha} + \frac{4}{32^\alpha} + \dots \\ &= \frac{2}{4^\alpha} + \frac{1}{8^\alpha} \left(1 + \frac{2}{2^\alpha} + \frac{4}{4^\alpha} + \dots\right) \\ &= \frac{2}{4^\alpha} + \frac{1}{8^\alpha} \frac{1}{1-2/2^\alpha} \\ &= \frac{2}{4^\alpha} + \frac{1}{8^\alpha-2 \cdot 4^\alpha} \\ &= \frac{2\cdot 8^\alpha - 3 \cdot 4^\alpha}{32^\alpha -2\cdot 16^\alpha} \\ &= \frac{2\cdot 2^\alpha - 3}{8^\alpha -2\cdot 4^\alpha}. \end{align*} $$ Letting $\beta = 2^\alpha$, we get the equation $2\beta - 3 = \beta^3 - 2\beta^2$, with solutions $\beta = 1, (1\pm \sqrt{13})/2$ and so $\alpha = 0, \log_2(1+\sqrt{13})-1$. The second solution is $\alpha \approx 1.20337$, and is the dominant one. We conclude that $S(n) \approx n^\alpha$, at least in the sense that $\log_n S(n) \to \alpha$. (See below for a more thorough argument.)

Since $S(n) \geq T(n/4)$ and $T(n) \geq S(n/2)$, also $\log_n T(n) \to \alpha$.


I have claimed that the recurrence for $S(n)$ implies a certain asymptotics for $S(n)$. Here is how to formally prove this using the Akra–Bazzi theorem. We can cut the recurrence after $k+2$ terms to obtain a lower bound recurrence: $$ S_k(n) = 2S_k(n/4) + S_k(n/8) + \dots + 2^kS_k(n/2^{k+3}). $$ Clearly $S(n) \geq S_k(n)$. The Akra–Bazzi theorem states that $S_k(n) = \Theta_k(n^{p_k})$, where $p_k$ is the unique solution of $$ \frac{2}{4^{p_k}} + \frac{1}{8^{p_k}} + \dots + \frac{2^k}{2^{(k+3)p_k}} = 1. $$ We conclude that $S(n) = \Omega_k(n^{p_k})$ for all $k$. As $k\to\infty$, it is not hard to check that $p_k \to \alpha$, and so $S(n) = \Omega_{\epsilon}(n^{\alpha-\epsilon})$ for all $\epsilon > 0$.

In order to obtain an estimate from above, we have to work a bit harder. Start with the expression $$ \begin{align*} T(n) &= S(n/2) + 2S(n/4) + \dots + 2^{k-1}S(n/2^k) + 2^kT(n/2^k) \\ &\leq S(n/2) + 2S(n/4) + \dots + 2^{k-1}S(n/2^k) + 2^kS(n/2^{k-2}), \end{align*} $$ since $T(m/4) \leq S(m)$. Now we can set up an upper bound recurrence: $$ S'_k(n) = 2S'_k(n/4) + S'_k(n/8) + \dots + 2^{k-1}S'_k(n/2^{k+2}) + 2^kS'_k(n/2^k). $$ Clearly $S'_k(n) \geq S(n)$. Again using the Akra–Bazzi theorem we can estimate $S'_k(n) = \Theta_k(n^{q_k})$, where $q_k$ is a solution of $$ \frac{2}{4^{p_q}} + \frac{1}{8^{p_q}} + \dots + \frac{2^{k-1}}{2^{(k+2)q_k}} + \frac{2^k}{2^{kq_k}} = 1. $$ Again we see that $q_k \to \alpha$, and so for all $\epsilon > 0$, $S(n) = O_\epsilon(n^{\alpha + \epsilon})$.

Together, upper and lower bound easily imply $\log_n S(n) \to \alpha$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22149

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback