Question

Find the solution to the recurrence relation,

\(f\left( n \right) = 3f\left( {\frac{n}{5}} \right) + 2{n^4}\),

When \(n\) is divisible by \(5\),

For \(n = {5^k}\)

Where \(k\) is a positive integer and

\(f\left( 1 \right) = 1\).

Short answer

The solution for the recurrence relation \(f\left( n \right) = 3f\left( {\frac{n}{5}} \right) + 2{n^4}\) is \(\frac{{625}}{{311}}{n^4} - \frac{{314}}{{311}}{n^{lo{g_5}n}}\).

Step-by-step solution

Given information

We have given that,

The\(k\)is a positive integer and\(f\left( 1 \right) = 1\).

The recurrence relation for\(n = {5^k}\)is,

\(f\left( n \right) = 3f\left( {\frac{n}{5}} \right) + 2{n^4}\)

Definition and formula to be used

In mathematics, the divide-and-conquer recurrence relations entails breaking down a huge problem into smaller subproblems and recursively solving each of them.

We will solve the problem by using the master’s theorem is,

\(f\left( n \right) = af\left( {\frac{n}{b}} \right) + c{n^d}\)

Here, \(f\left( n \right)\) is the number of operations required to solve the problem of size \(n\).

Calculation

Now, we will compare the function when \(n = {5^k}\) is,

\(f\left( n \right) = 3f\left( {\frac{n}{5}} \right) + 2{n^4}\),

By using the master’s theorem

Here, \(a = 3\), \(b\) is equal to \(5\) and \(c\) is equal to \(2\) and \(d\) is equal to \(4\).

We get,

\(f\left( n \right) = \frac{{{b^d}c}}{{{b^d} - a}}{n^d} + \left( {f\left( 1 \right) + \frac{{{b^d}c}}{{a - {b^d}}}} \right){n^k}\)

\( = \frac{{{5^4} \cdot 2}}{{{5^4} - 3}}{n^4} + \left( {1 + \frac{{{5^4} \cdot 2}}{{3 - {5^4}}}} \right){n^{{{\log }_5}n}}\)

\( = \frac{{625}}{{311}}{n^4} - \frac{{314}}{{311}}{n^{lo{g_5}n}}\)

Thus, the solution for the given recurrence relation is \(\frac{{625}}{{311}}{n^4} - \frac{{314}}{{311}}{n^{lo{g_5}n}}\).