0 votes 0 votes 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.$ Combinatory kenneth-rosen discrete-mathematics counting recurrence-relation descriptive + – admin asked May 9, 2020 admin 538 views answer comment Share Follow See 1 comment See all 1 1 comment reply Debapaul commented Jul 2, 2020 reply Follow Share How your GATE 2020 went? 0 votes 0 votes Please log in or register to add a comment.
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})$ Aman_Singh answered Aug 2, 2020 Aman_Singh comment Share Follow See all 0 reply Please log in or register to add a comment.