538 views

1 Answer

0 votes
0 votes
Here we have $f(n)=2f(n/3)+4$

a=2, b=3, c=4, d=0

By applying Master Theorem since $a>b^{d}$

$f(n)=o(n^{log_b{a}}) =o(n^{log_3{2}}) \approx o(n^{0.63})$

Related questions

0 votes
0 votes
1 answer
1
admin asked May 9, 2020
1,179 views
Solve the recurrence relation for the number of rounds in the tournament described in question $14.$
0 votes
0 votes
1 answer
2
admin asked May 9, 2020
513 views
How many rounds are in the elimination tournament described in question $14$ when there are $32$ teams?
1 votes
1 votes
2 answers
4
admin asked May 9, 2020
615 views
Find $f (n)$ when $n = 3k,$ where $f$ satisfies the recurrence relation $f (n) = 2f (n/3) + 4 \:\text{with}\: f (1) = 1.$