पुनरावृत्ति संबंध को हल करना टी (एन) = 3 टी (2 एन / 3) + सीएन - पुनरावृत्ति

मैं पुनरावृत्ति विधि द्वारा इस संबंध को हल करने की कोशिश कर रहा हूं।

मैं समझता हूं कि समाधान का पहला भाग है 3^rT(2/3)^r * n। लेकिन isn "इसके बाकी हिस्सों को नहीं cn + 3n + 5n + 7n .... ?

आप जो भी मदद दे सकें मैं उसका आभारी होऊंगा।

उत्तर:

यदि हम बार-बार पुन: स्थानापन्न होते हैं T:

बाद m पुनरावृत्तियों। हम कब रुकेंगे? यह मानते हुए कि रोक की स्थिति है n = 1:

इसलिए अंतिम परिणाम है:

इस परिणाम की पुष्टि करने के लिए कुछ संख्यात्मक परीक्षण:

N       T(N)
---------------------
1000    262143000
2000    1048574000
3000    3145725000
4000    8388604000
5000    20971515000
6000    25165818000
7000    29360121000
8000    67108856000
9000    75497463000
10000   83886070000

लॉग-लॉग प्लॉट:

ढाल m इस भूखंड का आकार ऐसा है T(N) = ϴ(N^m)। परिणाम m = 2.70562 बल्कि सैद्धांतिक मूल्य के करीब है 2.70951.