Return to Question

The goal is to get big $\Theta$ for $$T(n) = 2T\left(\frac{n}{3}\right) + 2T\left(\frac{2n}{3}\right)+n$$ I tried two approaches, but both failed:

1. Recursion tree. We see that $$\begin{align} \sum_{i = 0}^{\log_{3}(n)}n2^i & = \Theta(n^{1+\log_3(2)})\\ & \ll T(n) \\[1em] & \ll \sum_{i = 0}^{\log_{\frac{3}{2}}(n)} n2^i \\[0.5em] & = \Theta(n^{1+\log_{\frac{3}{2}}(2)}) \end{align}$$ but cannot, as I can see, get $\Theta(T(n))$ exactly.

2. Akra-Bazzi Theorem. We get through straightforward calculus that $T(n) = \Theta(n^p)$ where $2+2^{p+1} = 3^p$, as far as I can see there is no way to get a closed form for p from this equation (but it gives a numerical approximation consistent with 1, $p$ is about $2.19$ so that is good).

What I want is to find a closed form for p.

This is problem 2(m) from Jeffrey Erickson's notes on recurrences: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/99-recurrences.pdf

Any help is appreciated.

The goal is to get big $\Theta$ for $$T(n) = 2T\left(\frac{n}{3}\right) + 2T\left(\frac{2n}{3}\right)+n$$ I tried two approaches, but both failed:

1. Recursion tree. We see that $$\begin{align} \sum_{i = 0}^{\log_{3}(n)}n2^i & = \Theta(n^{1+\log_3(2)})\\ & \ll T(n) \\[1em] & \ll \sum_{i = 0}^{\log_{\frac{3}{2}}(n)} n2^i \\[0.5em] & = \Theta(n^{1+\log_{\frac{3}{2}}(2)}) \end{align}$$ but cannot, as I can see, get $\Theta(T(n))$ exactly.

2. Akra-Bazzi Theorem. We get through straightforward calculus that $T(n) = \Theta(n^p)$ where $2+2^{p+1} = 3^p$, as far as I can see there is no way to get a closed form for p from this equation (but it gives a numerical approximation consistent with 1, $p$ is about $2.19$ so that is good).

What I want is to find a closed form for $p$, one better than $2+2^{p+1}=3^p$. I believe such a closed form does exist, it might be found with domain transformations or something like that.

This is problem 2(m) from Jeffrey Erickson's notes on recurrences: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/99-recurrences.pdf

Any help is appreciated.

The goal is to get big $\Theta$ for $$T(n) = 2T\left(\frac{n}{3}\right) + 2T\left(\frac{2n}{3}\right)+n$$ I tried two approaches, but both failed:

1. Recursion tree. We see that $$\begin{align} \sum_{i = 0}^{\log_{3}(n)}n2^i & = \Theta(n^{1+\log_3(2)})\\ & \ll T(n) \\[1em] & \ll \sum_{i = 0}^{\log_{\frac{3}{2}}(n)} n2^i \\[0.5em] & = \Theta(n^{1+\log_{\frac{3}{2}}(2)}) \end{align}$$ but cannot, as I can see, get $\Theta(T(n))$ exactly.

2. Akra-Bazzi Theorem. We get through straightforward calculus that $T(n) = \Theta(n^p)$ where $2+2^{p+1} = 3^p$, as far as I can see there is no way to get a closed form for p from this equation (but it gives a numerical approximation consistent with 1, $p$ is about $2.19$ so that is good).

What I want is to find a closed form for p. Any help is appreciated.

The goal is to get big $\Theta$ for $$T(n) = 2T\left(\frac{n}{3}\right) + 2T\left(\frac{2n}{3}\right)+n$$ I tried two approaches, but both failed:

1. Recursion tree. We see that $$\begin{align} \sum_{i = 0}^{\log_{3}(n)}n2^i & = \Theta(n^{1+\log_3(2)})\\ & \ll T(n) \\[1em] & \ll \sum_{i = 0}^{\log_{\frac{3}{2}}(n)} n2^i \\[0.5em] & = \Theta(n^{1+\log_{\frac{3}{2}}(2)}) \end{align}$$ but cannot, as I can see, get $\Theta(T(n))$ exactly.

2. Akra-Bazzi Theorem. We get through straightforward calculus that $T(n) = \Theta(n^p)$ where $2+2^{p+1} = 3^p$, as far as I can see there is no way to get a closed form for p from this equation (but it gives a numerical approximation consistent with 1, $p$ is about $2.19$ so that is good).

What I want is to find a closed form for p.

This is problem 2(m) from Jeffrey Erickson's notes on recurrences: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/99-recurrences.pdf

Any help is appreciated.

The goal is to get an exact asymptotic for $$T(n) = 2T\left(\frac{n}{3}\right) + 2T\left(\frac{2n}{3}\right)+n$$ I tried two approaches, but both failed:

1. Recursion tree. We see that $$\begin{align} \sum_{i = 0}^{\log_{3}(n)}n2^i & = \Theta(n^{1+\log_3(2)})\\ & \ll T(n) \\[1em] & \ll \sum_{i = 0}^{\log_{\frac{3}{2}}(n)} n2^i \\[0.5em] & = \Theta(n^{1+\log_{\frac{3}{2}}(2)}) \end{align}$$ but cannot, as I can see, get $\Theta(T(n))$ exactly.

2. Akra-Bazzi Theorem. We get through straightforward calculus that $T(n) = \Theta(n^p)$ where $2+2^{p+1} = 3^p$, as far as I can see an unsolvable equation (but it gives a numerical approximation consistent with 1, so that is good).

Any help is appreciated.

The goal is to get big $\Theta$ for $$T(n) = 2T\left(\frac{n}{3}\right) + 2T\left(\frac{2n}{3}\right)+n$$ I tried two approaches, but both failed:

1. Recursion tree. We see that $$\begin{align} \sum_{i = 0}^{\log_{3}(n)}n2^i & = \Theta(n^{1+\log_3(2)})\\ & \ll T(n) \\[1em] & \ll \sum_{i = 0}^{\log_{\frac{3}{2}}(n)} n2^i \\[0.5em] & = \Theta(n^{1+\log_{\frac{3}{2}}(2)}) \end{align}$$ but cannot, as I can see, get $\Theta(T(n))$ exactly.

2. Akra-Bazzi Theorem. We get through straightforward calculus that $T(n) = \Theta(n^p)$ where $2+2^{p+1} = 3^p$, as far as I can see there is no way to get a closed form for p from this equation (but it gives a numerical approximation consistent with 1, $p$ is about $2.19$ so that is good).

What I want is to find a closed form for p. Any help is appreciated.