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

Question

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.$

Comments

How your GATE 2020 went?

Answer 1

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})$