Question

Suppose that the function \(f\) satisfies the recurrence relation \(f(n) = 2f(\sqrt n ) + 1\) whenever \(n\) is a perfect square greater than\(1\)and\(f(2) = 1\).

a) Find\(f(16)\).

b) Give a big- \(O\) estimate for\(f(n)\). (Hint: Make the substitution\(m = \log n\)).

Short answer

(a)The required function\(f(16) = 7\).

(b)The required function\(f(n) = O(\log n)\).

Step-by-step solution

Given information

The function \(f\) satisfies the recurrence relation\(f(n) = 2f(\sqrt n ) + 1\). Where\(n\)is a perfect square greater than\(1\)and\(f(2) = 1\).

Explain the Master theorem

The master theorem is a formula for solving recurrence relations of the form:\({\bf{T}}({\bf{n}}) = {\bf{aT}}({\bf{n}}/{\bf{b}}) + {\bf{f}}({\bf{n}})\), Where, \({\bf{n}} = \) the size of the input \({\bf{a}} = \) number of sub-problems in the recursion \({\rm{n}}/{\rm{b}} = \) size of each subproblem. All subproblems are assumed to have the same size.

Calculate the function\(f(16)\)

(a)

To find\(f(16)\):

\(f(16) = 2f(4) + 1\)

\(f(16) = 2(2f(2) + 1) + 1\)

\(\begin{array}{l}f(16) = 2(2 + 1) + 1\\f(16) = 7\end{array}\)

Calculate the value of\(f(n)\)by the Master theorem

(b)

Use the suggested substitution and let\(m = \log n\).

So,\({2^m} = n\)

Now, it will may be\(f(n) = f\left( {{2^m}} \right)\).

\(\begin{array}{l}f(n) = 2f\left( {\sqrt {{2^m}} } \right) + 1\\f(n) = 2f\left( {{2^{m/2}}} \right) + 1\end{array}\)

Re-write the function, for clarity, as\(g(m) = f\left( {{2^m}} \right)\).

And so, \(g(m) = 2g(m/2) + 1\).

Next, apply the Master theorem with\(a = 2,\,\,b = 2,\,\,c = 1,\,\,d = 0\):

\(\begin{array}{l}g(m) = O\left( {{m^{{{\log }_2}2}}} \right)\\g(m) = O(m)\end{array}\)

Hence,\(f(n) = O(\log n)\).