The solution of recurrence relation: T(n)=2T(sqrt(n) + log(n) is

To solve the recurrence T(n) = 2T(√n) + log n, we use the substitution method.

Let n = 2^k, so √n = 2^(k/2). Then T(2^k) = 2T(2^(k/2)) + k.

Define S(k) = T(2^k). The recurrence becomes S(k) = 2S(k/2) + k.

This is a standard divide-and-conquer recurrence. Using the recursion tree method:

At level 0: work = k

At level 1: work = 2 × (k/2) = k

At level 2: work = 4 × (k/4) = k

Each level contributes O(k) work.

Number of levels: k → k/2 → k/4 → ... → 1. This takes O(log k) levels.

Total work: O(k log k).

Substitute back: k = log n, so T(n) = O(log n log log n).

Thus, the solution is O(log n log log n).

हिन्दी उत्तर:

पुनरावृत्ति T(n) = 2T(√n) + log n को हल करने के लिए, हम उपस्थापन विधि का उपयोग करते हैं।

मान लीजिए n = 2^k, तो √n = 2^(k/2)। तब T(2^k) = 2T(2^(k/2)) + k।

S(k) = T(2^k) परिभाषित करें। पुनरावृत्ति S(k) = 2S(k/2) + k बन जाती है।

यह एक मानक विभाजन-और-जीत पुनरावृत्ति है। रिकर्शन ट्री विधि का उपयोग करके:

स्तर 0 पर: काम = k

स्तर 1 पर: काम = 2 × (k/2) = k

स्तर 2 पर: काम = 4 × (k/4) = k

प्रत्येक स्तर O(k) काम योगदान करता है।

स्तरों की संख्या: k → k/2 → k/4 → ... → 1। इसमें O(log k) स्तर लगते हैं।

कुल काम: O(k log k)।

वापस स्थापित करें: k = log n, इसलिए T(n) = O(log n log log n)।

इसलिए, समाधान O(log n log log n) है।