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

0 votes
31 views

Suppose that $f (n) = f (n/3) + 1$ when $n$ is a positive integer divisible by $3,$ and $f (1) = 1.$ Find

1. $f (3)$
2. $f (27)$
3. $f (729)$

1 Answer

0 votes
f(n)=f(n/3)+1                          f(1)=1

f(3)=f(3/3)+1 => f(1)+1 => 1+1=2

f(9)=f(3)+1 => 2+1=3

f(27)=f(9)+1 => 3+1=4

f(81)=f(27)+1=>5

f(243)=f(81)+1 => 6

f(729)=f(243)+1=>7

Related questions

0 votes
1 answer
1
259 views
Solve the recurrence relation for the number of rounds in the tournament described in question $14.$
0 votes
1 answer
2
93 views
How many rounds are in the elimination tournament described in question $14$ when there are $32$ teams?
0 votes
2 answers
3
113 views
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.
0 votes
1 answer
4
140 views
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.$