Asymptotic Runtime of Interrelated Functions

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*}
$$

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

StackExchange Computer Science Q#22149, answer score: 4