How does one convert a recurrence relation to a non-recursive function?
I am not sure about the substitution, recursion tree, and master method. Is there an easy way to do this?
[Math] How to convert a recurrence relation to a non recursive function
algorithmsrecurrence-relations
Related Solutions
$% Predefined Typography \newcommand{\paren} [1]{\left({#1}\right)} \newcommand{\bparen}[1]{\bigg({#1}\bigg)} \newcommand{\brace} [1]{\left\{{#1}\right\}} \newcommand{\bbrace}[1]{\bigg\{{#1}\bigg\}} \newcommand{\floor} [1]{\left\lfloor{#1}\right\rfloor} \newcommand{\bfloor}[1]{\bigg\lfloor{#1}\bigg\rfloor} \newcommand{\mag} [1]{\left\lVert{#1}\right\rVert} \newcommand{\bmag} [1]{\bigg\Vert{#1}\bigg\Vert} \newcommand{\abs} [1]{\left\vert{#1}\right\vert} \newcommand{\babs} [1]{\bigg\vert{#1}\bigg\vert} % \newcommand{\labelt}[2]{\underbrace{#1}_{\text{#2}}} \newcommand{\label} [2]{\underbrace{#1}_{#2}} \newcommand{\ulabelt}[2]{\overbrace{#1}_{\text{#2}}} \newcommand{\ulabel} [2]{\overbrace{#1}_{#2}} % \newcommand{\setcomp}[2]{\left\{~{#1}~~\middle \vert~~ {#2}~\right\}} \newcommand{\bsetcomp}[2]{\bigg\{~{#1}~~\bigg \vert~~ {#2}~\bigg\}} % \newcommand{\iint}[2]{\int {#1}~{\rm d}{#2}} \newcommand{\dint}[4]{\int_{#3}^{#4}{#1}~{\rm d}{#2}} \newcommand{\pred}[2]{\frac{\rm d}{{\rm d}{#2}}#1} \newcommand{\ind} [2]{\frac{{\rm d} {#1}}{{\rm d}{#2}}} \newcommand{\predp}[2]{\frac{\partial}{\partial {#2}}#1} \newcommand{\indp} [2]{\frac{{\partial} {#1}}{\partial {#2}}} \newcommand{\predn}[3]{\frac{\rm d}^{#3}{{\rm d}{#2}^{#3}}#1} \newcommand{\indn} [3]{\frac{{\rm d}^{#3} {#1}}{{\rm d}{#2}^{#3}}} % \newcommand{\ii}{{\rm i}} \newcommand{\ee}{{\rm e}} \newcommand{\exp}[1] { {\rm e}^{\large{#1}} } % \newcommand{\and} {~\text{and}~} \newcommand{\xor} {~\text{xor}~} \newcommand{\or} {~\text{or}~} \newcommand{\T} {\text{True}} \newcommand{\F} {\text{False}} % \newcommand{\red} [1]{\color{red}{#1}} \newcommand{\blue} [1]{\color{blue}{#1}} \newcommand{\green}[1]{\color{green}{#1}} $
$$T(n) = T \paren{ \frac{n}{3} } + T\paren{ \frac{2n}{3} } + n$$ $$\Downarrow$$ $$T(n) = \Theta(n~\log n)$$
You can just use strong induction on the definition directly:
For some positive $k_1$ and $k_2$, and $n_0$: $$f \in \Theta(g)$$ is defined as $$\forall n > n_0 \quad k_1~g(n) \le f(n) \le k_2 ~ g(n)$$
So inductively prove:
$$k_1 ~n~\log(n) \le T(n) \le k_2~ n~\log(n)$$ $$k_1 ~n~\log(n) \le T\left(\frac{n}{3}\right) + T\left(\frac{2n}{3}\right) + n \le k_2~ n~\log(n) \tag{A1}$$
So we are going to need the inductive assumptions that
$$k_1 ~\frac n3 ~\log \paren{\frac n3} \le T\paren{\frac{n}{3}} \le k_2~ \frac n3~\log \paren{\frac n3} \tag{A2}$$
$$k_1 ~\frac {2n}3 ~\log \paren{\frac {2n}3} \le T\paren{\frac{2n}{3}} \le k_2~ \frac {2n}3~\log \paren{\frac {2n}3} \tag{A3}$$
So applying (A2) and (A3) to (A1), it leaves 2 statements to prove, find $k_1$ and $k_2$ such that both of the following hold:
$$\begin{align} k_1 ~n~\log(n) ~\le~ & k_1 ~\frac n3 ~\log \paren{\frac n3} + k_1 ~\frac {2n}3 ~\log \paren{\frac {2n}3} + n \tag{B1} \\ & k_2~ \frac n3~\log \paren{\frac n3} + k_2~ \frac {2n}3~\log \paren{\frac {2n}3} + n ~\le~ k_2 ~ n~\log(n) \tag{C1} \end{align}$$
(B1) and (C1) may be simplified by combining the $n$ and $n~\log n$ expressions together:
$$0 ~\le~ \frac 13 \paren{k_1 \log\paren{\frac 13} + 2 k_1 \log\paren{\frac 23} + 3 } n \tag{B2}$$ $$0 ~\le~ -\frac 13 \paren{k_2 \log\paren{\frac 13} + 2 k_2 \log\paren{\frac 23} + 3} n \tag{C2}$$
So very small $k_1$ satisfy (B2) and very large $k_2$ satisfy (C2), so the induction is finished and the proposition is established.
Best Answer
The master method applies only in some situations (see the link); when it does apply, it tells you what you'll get if you use the recursion tree method.
The substitution method works especially well for recursions like $$ f(n) = f(n-1) + g(n), \quad f(n) = f(n/2) + g(n), $$ and in any other situation in which $f(n)$ depends on at most one earlier value of $f$. In some cases you can look up the answer. For example, there is the "polynomial method", which is a recipe for solving recurrences of the type $$ f(n) = \begin{cases} f(n-1) + P(n) & n > n_0, \\ C & n = n_0. \end{cases} $$ For example, if you define $f(0) = 0$ and $f(n) = f(n-1) + 2n - 1$ then you get using this method that $$ f(n) = n^2. $$ A vast generalization is Gosper's algorithm, see also A=B.