# Kenneth Rosen Edition 7th Exercise 8.3 Question 9 (Page No. 535)

25 views

Suppose that $f (n) = f (n/5) + 3n^{2}$ when $n$ is a positive integer divisible by $5, \:\text{and}\: f (1) = 4.$ Find

1. $f (5)$
2. $f (125)$
3. $f (3125)$

f(5):

$f(5) = f(5/5) + 3(5)^{2}$

=$f(1) + 3(25)$

= $4 + 75$

= $79$

f(125):

$f(25) = f(25/5) + 3(25)^{2}$

= $f(5) + 3(625)$

= $79 + 1875$

= $1954$

$f(125) = f(125/5) + 3(125)^{2}$

= $f(25) + 3(15625)$

= $1954 + 46875$

= $48829$

f(3125):

$f(625) = f(625/5) + 3(625)^{2}$

= $f(125) + 3(390625)$

= $48829 + 1171875$

= $1220704$

$f(3125) = f(3125/5) + 3(3125)^{2}$

=$f(625) + 3(9765625)$

= $1220704 + 29296875$

= $30517579$

## Related questions

1
259 views
Solve the recurrence relation for the number of rounds in the tournament described in question $14.$
How many rounds are in the elimination tournament described in question $14$ when there are $32$ teams?
Suppose that there are $n = 2^{k}$ teams in an elimination tournament, where there are $\frac{n}{2}$ games in the first round, with the $\frac{n}{2} = 2^{k-1}$ winners playing in the second round, and so on. Develop a recurrence relation for the number of rounds in the tournament.
Give a big-O estimate for the function $f$ given below if $f$ is an increasing function. $f (n) = 2f (n/3) + 4 \:\text{with}\: f (1) = 1.$