Question

Find the solution to the recurrence relation,

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

For \(n = {2^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) = f\left( {\frac{n}{2}} \right) + {n^2}\) is \(\frac{{4{n^2} - 1}}{3}\).

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 = {2^k}\)is,

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

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 use the formula of Divide-and conquer recurrence relation is,

\(f\left( n \right) = af\left( {\frac{n}{b}} \right) + g\left( n \right)\)

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 = {2^k}\) is,

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

By using the formula of Divide-and-conquer recurrence relation,

Here, \(a = 1\), \(b\) is equal to \(2\) and \(g\left( n \right)\) is equal to \({n^2}\).

We get,

\(f\left( n \right) = {1^k}f\left( 1 \right) + \sum\limits_{j = 0}^{k - 1} {{1^j}g} \left( {\frac{{{2^k}}}{{{2^j}}}} \right)\)

\( = 1\left( {\left( {\frac{{{2^k}}}{{{2^0}}}} \right) + \left( {\frac{{{2^k}}}{{{2^1}}}} \right) + .... + {{\left( {\frac{{{2^k}}}{{{2^{k - 1}}}}} \right)}^2}} \right)\)

\( = 1 + \frac{{{2^2}\left( {{2^{2k}} - 1} \right)}}{{{{\left( 2 \right)}^2} - 1}}\)

\( = \frac{{4{n^2} - 1}}{3}\)

Thus, the solution for the given recurrence relation is \(\frac{{4{n^2} - 1}}{3}\).