سلام من یه سوال مطرح کردم اما به دلیل اینکه سوال درست بیان نشده بود . موضوع توسط مدیر محترم بسته شد . حالا دوباره مطرحش می کنم.
متن سوال :

در رابطه بازگشتی $T(n)= 9T(\frac{n}{3}) f(n)$ به ازای چند تا از عبارت های$g(n)$ زیر ، دست کم یک تابع برای $f(n)$ وجود دارد به طوری که $T(n) = \Theta (g(n))$ ؟


گزینه ی اول : ۱ / گزینه ی دوم : ۲ / گزینه ی سوم : ۳ / گزینه ی چهارم : ۴



جواب :
طبق قضیه ی اصلی $9T(\frac{n}{3})$ داریم : $n^{log_{3}^{9}} = n^{2}$

حالا اگر $f(n) = n^{3}$ آنگاه $T(n) = n^{3}$
اگر $f(n) = n^{2}$ آنگاه $T(n) = n^{2} log n$
اگر $f(n) = n^{2} log n$ آنگاه $T(n) = n^{2} log^{2} n$

مشکل من در مورد خط قبلی هست که به نظر من طبق قضیه اصلی $T(n) = n^{2}logn$ خواهد شد و نه $T(n) = n^{2} log^{2} n$. چون در اینجا $f(n)$ بزرگتر از $n^{2}$ است . در ضمن کلید سنجش هم گزینه ی ۳ است . و همچنین این راه حل مربوط به موسسه ی ماهان است.

از کمکتون ممنونم.