حل تشریحی سوال شماره 37 دروس مشترک

رابطه بازگشتی $T\left(n\right)=8T\left(n/2\right)+f\left(n\right)$ را در نظر بگیرید. فرض کنید تابع $g\left(n\right)$ یکی از توابع $n,n\log n,n^3,n^4\log n$باشد. به ازای چند تا از این ۴ تابع تابع $f\left(n\right)$ وجود دارد، به طوری که $T\left(n\right)=O\left(g\left(n\right)\right)$ ؟