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

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


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



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

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

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

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