1 votes 1 votes Find $f (n)$ when $n = 3k,$ where $f$ satisfies the recurrence relation $f (n) = 2f (n/3) + 4 \:\text{with}\: f (1) = 1.$ Combinatory kenneth-rosen discrete-mathematics counting recurrence-relation descriptive + – admin asked May 9, 2020 admin 636 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
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! manish_dt answered May 9, 2020 manish_dt comment Share Follow See 1 comment See all 1 1 comment reply Eric Fischer commented May 26, 2020 reply Follow Share for me it is also helpful, many thanks! 0 votes 0 votes Please log in or register to add a comment.
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} ).$ Mohit Kumar 6 answered May 21, 2020 Mohit Kumar 6 comment Share Follow See all 0 reply Please log in or register to add a comment.