2 answered in more detail edited Jan 19 '17 at 11:07 quicksort 3,90211 gold badge44 silver badges2121 bronze badges Let $$\mathcal{S}(n)$$ be the running time of foo and $$\mathcal{T}(n)$$ be the running time of bar. We have the following system of recursive equations: $$\left\{ \begin{array}{r c l} \mathcal{S}(n) & = & \mathcal{S}(n-1) + \mathcal{T}(n) + \Theta(1)\\ \mathcal{T}(n) & = & \mathcal{S}(n-1) + \mathcal{T}(n/2) + \Theta(1) \end{array} \right.$$ By isolating $$\mathcal{T}(n)$$ in the first and $$\mathcal{S}(n)$$ in the second, we obtain: $$\left\{ \begin{array}{r c l} \mathcal{S}(n-1) & = & \mathcal{T}(n) - \mathcal{T}(n/2) + \Theta(1)\\ \mathcal{T}(n) & = & \mathcal{S}(n) - \mathcal{S}(n-1) + \Theta(1) \end{array} \right.$$ We canI will now substitute, obtaining two separate recursive equations. I'll leavesolve for you to check that $$\mathcal{S}(n), \mathcal{T}(n) \in \Theta(2^n)$$$$\mathcal{T}$$, consistently with a similar reasoning holding for $$\mathcal{S}$$. Since: $$\mathcal{S}(n-1) = \mathcal{T}(n) - \mathcal{T}(n/2) + \Theta(1)$$ We also have that: $$\mathcal{S}(n) = \mathcal{T}(n+1) - \mathcal{T}((n+1)/2) + \Theta(1)$$ Therefore the intuition one has looking atfirst equation of our original system becomes: $$\mathcal{T}(n+1) - \mathcal{T}((n+1)/2) = \mathcal{T}(n) + \mathcal{T}(n) - \mathcal{T}(n/2) + \Theta(1)$$ Reordering the codeterms: $$\mathcal{T}(n+1) = 2 \mathcal{T}(n) - \mathcal{T}(n/2) + \mathcal{T}((n+1)/2) + \Theta(1)$$ Since $$(n+1)/2$$ is either $$n/2$$ or $$n/2+1$$, it must be that $$\mathcal{T}((n+1)/2) - \mathcal{T}(n/2) \ge 0$$ which means: $$\mathcal{T}(n+1) \ge 2 \mathcal{T}(n) + \Theta(1)$$ and: $$\mathcal{T}(n) \in \Omega(2^n)$$ We can check the other arrow (i.e. $$\mathcal{T}(n) \in \mathcal{O}(2^n)$$) by induction. Let $$\mathcal{S}(n)$$ be the running time of foo and $$\mathcal{T}(n)$$ be the running time of bar. We have the following system of recursive equations: $$\left\{ \begin{array}{r c l} \mathcal{S}(n) & = & \mathcal{S}(n-1) + \mathcal{T}(n) + \Theta(1)\\ \mathcal{T}(n) & = & \mathcal{S}(n-1) + \mathcal{T}(n/2) + \Theta(1) \end{array} \right.$$ By isolating $$\mathcal{T}(n)$$ in the first and $$\mathcal{S}(n)$$ in the second, we obtain: $$\left\{ \begin{array}{r c l} \mathcal{S}(n-1) & = & \mathcal{T}(n) - \mathcal{T}(n/2) + \Theta(1)\\ \mathcal{T}(n) & = & \mathcal{S}(n) - \mathcal{S}(n-1) + \Theta(1) \end{array} \right.$$ We can now substitute, obtaining two separate recursive equations. I'll leave for you to check that $$\mathcal{S}(n), \mathcal{T}(n) \in \Theta(2^n)$$, consistently with the intuition one has looking at the code. Let $$\mathcal{S}(n)$$ be the running time of foo and $$\mathcal{T}(n)$$ be the running time of bar. We have the following system of recursive equations: $$\left\{ \begin{array}{r c l} \mathcal{S}(n) & = & \mathcal{S}(n-1) + \mathcal{T}(n) + \Theta(1)\\ \mathcal{T}(n) & = & \mathcal{S}(n-1) + \mathcal{T}(n/2) + \Theta(1) \end{array} \right.$$ By isolating $$\mathcal{T}(n)$$ in the first and $$\mathcal{S}(n)$$ in the second, we obtain: $$\left\{ \begin{array}{r c l} \mathcal{S}(n-1) & = & \mathcal{T}(n) - \mathcal{T}(n/2) + \Theta(1)\\ \mathcal{T}(n) & = & \mathcal{S}(n) - \mathcal{S}(n-1) + \Theta(1) \end{array} \right.$$ I will now solve for $$\mathcal{T}$$, with a similar reasoning holding for $$\mathcal{S}$$. Since: $$\mathcal{S}(n-1) = \mathcal{T}(n) - \mathcal{T}(n/2) + \Theta(1)$$ We also have that: $$\mathcal{S}(n) = \mathcal{T}(n+1) - \mathcal{T}((n+1)/2) + \Theta(1)$$ Therefore the first equation of our original system becomes: $$\mathcal{T}(n+1) - \mathcal{T}((n+1)/2) = \mathcal{T}(n) + \mathcal{T}(n) - \mathcal{T}(n/2) + \Theta(1)$$ Reordering the terms: $$\mathcal{T}(n+1) = 2 \mathcal{T}(n) - \mathcal{T}(n/2) + \mathcal{T}((n+1)/2) + \Theta(1)$$ Since $$(n+1)/2$$ is either $$n/2$$ or $$n/2+1$$, it must be that $$\mathcal{T}((n+1)/2) - \mathcal{T}(n/2) \ge 0$$ which means: $$\mathcal{T}(n+1) \ge 2 \mathcal{T}(n) + \Theta(1)$$ and: $$\mathcal{T}(n) \in \Omega(2^n)$$ We can check the other arrow (i.e. $$\mathcal{T}(n) \in \mathcal{O}(2^n)$$) by induction. 1 answered Jan 18 '17 at 12:05 quicksort 3,90211 gold badge44 silver badges2121 bronze badges Let $$\mathcal{S}(n)$$ be the running time of foo and $$\mathcal{T}(n)$$ be the running time of bar. We have the following system of recursive equations: $$\left\{ \begin{array}{r c l} \mathcal{S}(n) & = & \mathcal{S}(n-1) + \mathcal{T}(n) + \Theta(1)\\ \mathcal{T}(n) & = & \mathcal{S}(n-1) + \mathcal{T}(n/2) + \Theta(1) \end{array} \right.$$ By isolating $$\mathcal{T}(n)$$ in the first and $$\mathcal{S}(n)$$ in the second, we obtain: $$\left\{ \begin{array}{r c l} \mathcal{S}(n-1) & = & \mathcal{T}(n) - \mathcal{T}(n/2) + \Theta(1)\\ \mathcal{T}(n) & = & \mathcal{S}(n) - \mathcal{S}(n-1) + \Theta(1) \end{array} \right.$$ We can now substitute, obtaining two separate recursive equations. I'll leave for you to check that $$\mathcal{S}(n), \mathcal{T}(n) \in \Theta(2^n)$$, consistently with the intuition one has looking at the code.