in Combinatory
610 views
1 vote
1 vote
Find $f (n)$ when $n = 3k,$ where $f$ satisfies the recurrence relation $f (n) = 2f (n/3) + 4 \:\text{with}\: f (1) = 1.$
in Combinatory
by
610 views

2 Answers

0 votes
0 votes

- Solve the given recurrence relation by backward substitution, This is one approach,

 Reference: http://web.deu.edu.tr/halil.oruc/M100FFA-05.pdf---> Problem 6a with solution

   Hope this helps!

1 comment

for me it is also helpful, many thanks!
0
0
0 votes
0 votes

Use Master Theorem with$ a = 2, b = 3, c = 4, d = 0$.

Since $a > b^{d}, (d<log_{b}a)$

we know that f(n) is $O(n^{ log_{b }a} ) = O(n ^{log_{3} 2} ).$

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true