Question

Give a big- \(O\) estimate for the function\(f\)in Exercise\(36\)if\(f\)is an increasing function.

Short answer

It is concluded that\(f(n) = 3{n^{3/2}} - 2 \cdot {n^2}\)is\(O\left( {{n^2}} \right)\).

Step-by-step solution

Given information

\(\begin{array}{c}f(n) = 8f(n/4) + {n^2}\\f(1) = 1\end{array}\)

Define the Recursive formula

A recursive formula is a formula that defines any term of a sequence in terms of its preceding terms.

Use the Recursive formula to find\(f(n)\)

Let \({a_k} = f\left( {{4^k}} \right)\) and use \(n = {4^k}\)

\(\begin{array}{l}{a_k} = 8{a_{k - 1}} + {4^{2k}}\\{a_k} = 8{a_{k - 1}} + {16^k}\left( {{4^0}} \right)\\{a_o} = f(1)\\{a_o} = 1\end{array}\)

Let \({a_k} = r\) and \({a_{k - 1}} = 1\)

\(r = 8\)(Root Characteristic equation)

The solution of the recurrence relation is of the form \({a_n} = {\alpha _1}r_1^n + {\alpha _2}r_2^n\) when \({r_1}\)and\({r_2}\)the distinct roots of the characteristic equation.

\(a_k^{(h)} = \alpha \cdot {8^k}\)

\(F(k) = {16^k}\)

If \(F(n) = \left( {{b_t}{n^t} + {b_{t - 1}}{n^{t - 1}} + \ldots + {b_1}n + {b_0}} \right){s^n}\) and \(s\) is not \({\bf{a}}\)root of the characteristic equation, then \(\left( {{p_t}{n^t} + {p_{t - 1}}{n^{t - 1}} + \ldots + {p_1}n + {p_0}} \right){s^n}\) is the particular solution.

\(a_k^{(p)} = {p_0} \cdot {16^k}\)

The particular solution needs to satisfy the recurrence relation:

\(\begin{array}{l}{a_n} = 8{a_{k - 1}} + {16^k}\\{p_0}.{a_n} = 8{p_0} \cdot {16^{k - 1}} + {16^k}\end{array}\)

\(\begin{array}{l}8{p_0} = 16\\{p_0} = 2\end{array}\)

Thus, the particular solution then becomes:

\(\begin{array}{l}a_k^{(p)} = {p_0} \cdot {16^k}\\a_k^{(p)} = 2 \cdot {16^k}\end{array}\)

The solution of the non-homogeneous recurrence relation is the sum of the solution of the homogeneous recurrence relation and the particular solution.

\({a_k} = \alpha \cdot {8^k} - 2 \cdot {16^k}\)

Check the solution that satisfies the initial condition

The solution needs to satisfy the initial condition \({a_0} = 1\) :

\(3 = \alpha \)

Then use \({a_k} = f\left( {{4^k}} \right),n = {4^k}\) and \(k = {\log _4}n\) :

\(\begin{array}{l}f(n) = f\left( {{4^k}} \right)\\f(n) = 3 \cdot {8^k} - 2 \cdot {16^k}\\f(n) = 3{n^{3/2}} - 2 \cdot {n^2}\end{array}\)

Finally,\(f(n) = 3{n^{3/2}} - 2 \cdot {n^2}\) is\(O\left( {{n^2}} \right)\).