সংক্ষিপ্ত বিবরণ
মাস্টার থিওরেমের এক্সটেনশন যা রিকারেন্স রিলেশন `T(n) = aT(n/b) + Θ(nᵏ logᵖ n)`-এর টাইম কমপ্লেক্সিটি বের করতে সাহায্য করে।
সাধারণ রিকারেন্স ফর্ম
T(n) = a T(n/b) + Θ(nᵏ logᵖ n)
- a = সাব-প্রব্লেমের সংখ্যা (a > 0)
- b = সাব-প্রব্লেমের সাইজ ফ্যাক্টর (b > 1)
- k ≥ 0, p = বাস্তব সংখ্যা
কেস অনুযায়ী সমাধান
| শর্ত | টাইম কমপ্লেক্সিটি |
|---|---|
| a > bᵏ | Θ(n^{log_b a}) |
| a = bᵏ |
|
| a < bᵏ |
|
উদাহরণ
- বাইনারি সার্চ: T(n) = T(n/2) + Θ(1) → Θ(log n)
- মার্জ সর্ট: T(n) = 2T(n/2) + Θ(n) → Θ(n log n)
