2 answered in more detail
source | link

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
source | link

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.