Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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*} $$
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$.
Here is one approach. Plug in the definition of $T(n)$ into your first equation, and we get
$$S(n) = 2S(n/4) + S(n/8) + 2T(n/8).$$
Now plug in again and we get
$$S(n) = 2S(n/4) + S(n/8) + 2S(n/16) + 4T(n/16).$$
Keep plugging in and eventually we get
$$S(n) = 2S(n/4) + S(n/8) + 2S(n/16) + 4S(n/32) + 8S(n/64) + \dots + O(1).$$
Now solve that recurrence relation for $S(n)$, noting that now you have a single function (you don't have two interrelated functions any longer).
Use the substitution $n = 2^k$, the result is a system of linear recurrences that is easy to solve.
This answer expands on vonbrand's suggestion. Define $s(m) = S(2^m)$ and $t(m) = T(2^m)$. Then $$ \begin{align*} s(m) &= 2s(m-2) + t(m-2), \\ t(m) &= s(m-1) + 2t(m-1). \end{align*} $$ We write this in matrix notation: $$ \begin{pmatrix} s(m) \\ t(m) \\ s(m-1) \\ t(m-1) \end{pmatrix} = \begin{pmatrix} 0 & 0 & 2 & 1 \\ 1 & 2 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix} \begin{pmatrix} s(m-1) \\ t(m-1) \\ s(m-2) \\ t(m-2) \end{pmatrix} $$ The eigenvalues of this matrix are $(1 \pm \sqrt{13})/2,1,0$; the Perron–Frobenius eigenvalue is $(1+\sqrt{13})/2$, and its eigenvector is strictly positive. This means that asymptotically, $s(m),t(m) = \Theta(((1+\sqrt{13})/2)^m)$. Substituting $n = 2^m$, we obtain $S(n),T(n) = \Theta(n^\alpha)$, where $\alpha = \log_2 \frac{1+\sqrt{13}}{2}$.
We can find the exact constants by diagonalizing the matrix: $$ \begin{pmatrix} 0 & 0 & 2 & 1 \\ 1 & 2 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & -1 & \tfrac{1}{2}(5+\sqrt{13}) & \tfrac{1}{2}(5-\sqrt{13}) \\ 0 & 1 & \tfrac{1}{2}(1-\sqrt{13}) & \tfrac{1}{2}(1+\sqrt{13}) \\ -1 & -1 & \tfrac{1}{2}(-3-\sqrt{13}) & \tfrac{1}{2}(-3+\sqrt{13}) \\ 2 & 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & \tfrac{1}{2}(1-\sqrt{13}) & 0 \\ 0 & 0 & 0 & \tfrac{1}{2}(1+\sqrt{13}) \end{pmatrix} \begin{pmatrix} 0 & -\tfrac{1}{3} & \tfrac{1}{3} & \tfrac{2}{3} \\ -\tfrac{1}{3} & \tfrac{1}{3} & -\tfrac{2}{3} & -\tfrac{1}{3} \\ \tfrac{-3+3\sqrt{13}}{18\sqrt{13}} & \tfrac{-9+3\sqrt{13}}{8\sqrt{13}} & -\tfrac{2}{3\sqrt{13}} & -\tfrac{1}{3\sqrt{13}} \\ \tfrac{3+3\sqrt{13}}{18\sqrt{13}} & \tfrac{9+3\sqrt{13}}{8\sqrt{13}} & \tfrac{2}{3\sqrt{13}} & \tfrac{1}{3\sqrt{13}} \end{pmatrix} $$ Therefore $$ \begin{align*} \begin{pmatrix} s(m+1) \\ t(m+1) \\ s(m) \\ t(m) \end{pmatrix} &= \begin{pmatrix} 0 & 0 & 2 & 1 \\ 1 & 2 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix}^m \begin{pmatrix} s(1) \\ t(1) \\ s(0) \\ t(0) \end{pmatrix} \\ &= \begin{pmatrix} 0 & -1 & \tfrac{1}{2}(5+\sqrt{13}) & \tfrac{1}{2}(5-\sqrt{13}) \\ 0 & 1 & \tfrac{1}{2}(1-\sqrt{13}) & \tfrac{1}{2}(1+\sqrt{13}) \\ -1 & -1 & \tfrac{1}{2}(-3-\sqrt{13}) & \tfrac{1}{2}(-3+\sqrt{13}) \\ 2 & 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & (\tfrac{1}{2}(1-\sqrt{13}))^m & 0 \\ 0 & 0 & 0 & (\tfrac{1}{2}(1+\sqrt{13}))^m \end{pmatrix} \begin{pmatrix} 0 & -\tfrac{1}{3} & \tfrac{1}{3} & \tfrac{2}{3} \\ -\tfrac{1}{3} & \tfrac{1}{3} & -\tfrac{2}{3} & -\tfrac{1}{3} \\ \tfrac{-1+\sqrt{13}}{6\sqrt{13}} & \tfrac{-3+\sqrt{13}}{6\sqrt{13}} & -\tfrac{2}{3\sqrt{13}} & -\tfrac{1}{3\sqrt{13}} \\ \tfrac{1+\sqrt{13}}{6\sqrt{13}} & \tfrac{3+\sqrt{13}}{6\sqrt{13}} & \tfrac{2}{3\sqrt{13}} & \tfrac{1}{3\sqrt{13}} \end{pmatrix} \begin{pmatrix} s(1) \\ t(1) \\ s(0) \\ t(0) \end{pmatrix} \\ &= \begin{pmatrix} 0 & -1 & \tfrac{1}{2}(5+\sqrt{13}) & \tfrac{1}{2}(5-\sqrt{13}) \\ 0 & 1 & \tfrac{1}{2}(1-\sqrt{13}) & \tfrac{1}{2}(1+\sqrt{13}) \\ -1 & -1 & \tfrac{1}{2}(-3-\sqrt{13}) & \tfrac{1}{2}(-3+\sqrt{13}) \\ 2 & 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} 0 \\ \tfrac{1}{3} (-s(1)+t(1)-2s(0)-t(0)) \\ \frac{(\tfrac{1}{2}(1-\sqrt{13}))^m}{6\sqrt{13}} ((-1+\sqrt{13})s(1)+(-3+\sqrt{13})t(1)-4s(0)-2t(0)) \\ \frac{(\tfrac{1}{2}(1+\sqrt{13}))^m}{6\sqrt{13}} ((1+\sqrt{13})s(1)+(3+\sqrt{13})t(1)+4s(0)+2t(0)) \end{pmatrix} \end{align*} $$ Finally, $$ \begin{align*} s(m) &= -\tfrac{1}{3} (-s(1)+t(1)-2s(0)-t(0)) -\tfrac{1}{2}(3+\sqrt{13})\frac{(\tfrac{1}{2}(1-\sqrt{13}))^m}{6\sqrt{13}} ((-1+\sqrt{13})s(1)+(-3+\sqrt{13})t(1)-4s(0)-2t(0)) + \tfrac{1}{2}(\sqrt{13}-3) \frac{(\tfrac{1}{2}(1+\sqrt{13}))^m}{6\sqrt{13}} ((1+\sqrt{13})s(1)+(3+\sqrt{13})t(1)+4s(0)+2t(0)), \\ t(m) &= \tfrac{1}{3} (-s(1)+t(1)-2s(0)-t(0)) +\frac{(\tfrac{1}{2}(1-\sqrt{13}))^m}{6\sqrt{13}} ((-1+\sqrt{13})s(1)+(-3+\sqrt{13})t(1)-4s(0)-2t(0)) + \frac{(\tfrac{1}{2}(1+\sqrt{13}))^m}{6\sqrt{13}} ((1+\sqrt{13})s(1)+(3+\sqrt{13})t(1)+4s(0)+2t(0)). \end{align*} $$
