complexity theory - T(n) = T(n/2) + T(n/4) + O(1), what is T(n)? -

इस पुनरावृत्ति को कैसे हल करें: T (n) = टी (एन / 2) + टी (n / 4 ) + ओ (1)

ऐसा लगता नहीं है जैसे मास्टर विधि मदद करेगा, क्योंकि यह T (n) = aT (n / b) के रूप में नहीं है + F (n) । और मुझे कुछ समय तक अटक गई।

मास्टर विधि की तुलना में अधिक शक्तिशाली विधि है।

चूंकि 'गैर-पुनरावर्ती' शब्द हे (1) है, यह समीकरण हल करने के बराबर है

1/2 ^ p + 1/4 ^ p = 1

और आप जो भी उत्तर प्राप्त करेंगे वो हो जाएगा टी (एन) = थीटा (एन ^ पी)

मेरा मानना ​​है कि उपर्युक्त को हल करना (< कोड> 1/2 ^ पी ) हमें p = log_2 phi देता है, जहां PHI सुनहरा अनुपात है।

कम्प्यूटिंग जो हमें T (n) देता है, = थीटा (n ^ 0.694 ...)