Understanding the Recurrence Relation

The given recurrence relation is $T(n) = 2T(\sqrt{n}) + \lg(n)$. We are asked to determine its Big O complexity, which is a way to describe the upper bound on how the running time $T(n)$ grows as the input size $n$ increases. This specific form, where the argument of the function $T$ is $\sqrt{n}$, is not directly solvable using the standard Master Theorem form $T(n) = aT(n/b) + f(n)$. We need a different approach, typically a change of variables.

The presence of $\sqrt{n}$ and $\lg(n)$ suggests that a substitution involving logarithms might simplify the relation. Let's proceed with a change of variables.

Change of Variables for Recurrence T(n)

To handle the $\sqrt{n}$ term, a common technique is to express $n$ as a power of a base, such as 2. Let $n = 2^k$. If $n = 2^k$, then taking the base-2 logarithm of both sides gives $\log_2 n = \log_2 (2^k)$, which simplifies to $k = \log_2 n$. In many contexts, $\lg n$ is used to denote $\log_2 n$, so we have $k = \lg n$.

Now, let's evaluate the $\sqrt{n}$ term using this substitution: $\sqrt{n} = \sqrt{2^k} = (2^k)^{1/2} = 2^{k/2}$.

The $\lg(n)$ term becomes: $\lg(n) = \lg(2^k) = k \lg(2)$. If $\lg$ means $\log_2$, then $\lg(2) = 1$, so $\lg(n) = k$.

Let's define a new recurrence relation in terms of $k$. Let $S(k) = T(2^k)$. Since $n=2^k$, $T(n)$ becomes $T(2^k)$ which is $S(k)$. The term $T(\sqrt{n})$ becomes $T(2^{k/2})$, which is $S(k/2)$ by our definition of $S$.

Substitute these into the original recurrence $T(n) = 2T(\sqrt{n}) + \lg(n)$: $S(k) = 2S(k/2) + k$.

This transformed recurrence $S(k) = 2S(k/2) + k$ is now in the standard form suitable for the Master Theorem.

Applying the Master Theorem to S(k)

The Master Theorem applies to recurrences of the form $S(k) = aS(k/b) + f(k)$. Comparing our transformed recurrence $S(k) = 2S(k/2) + k$ with the standard form, we identify the parameters:

• $a = 2$ (number of recursive calls)
• $b = 2$ (input size is divided by this factor)
• $f(k) = k$ (cost of the non-recursive part)

Now, we compute $\log_b a$: $\log_b a = \log_2 2 = 1$.

We compare $f(k)$ with $k^{\log_b a}$. $f(k) = k$. $k^{\log_b a} = k^1 = k$.

Since $f(k) = k$ and $k^{\log_b a} = k$, we see that $f(k) = \Theta(k^{\log_b a})$. This matches the conditions for Case 2 of the Master Theorem.

Master Theorem Case 2 Analysis

Case 2 of the Master Theorem states that if $f(k) = \Theta(k^{\log_b a} \lg^p k)$ for some constant $p \ge 0$, then the solution is $S(k) = \Theta(k^{\log_b a} \lg^{p+1} k)$.

In our case, $f(k) = k$. We can write $k = k^1 \cdot \lg^0 k$. So, we have $k^{\log_b a} = k^1$ and $p = 0$.

Applying the formula for Case 2: $S(k) = \Theta(k^1 \lg^{0+1} k) = \Theta(k \lg k)$.

Converting Back to Original Variable n for T(n) Complexity

We have found the complexity of $S(k)$ in terms of $k$. The original recurrence relation is $T(n)$, so we need to express the result in terms of $n$. We used the substitution $k = \lg n$.

Substitute $k = \lg n$ into the solution for $S(k)$: $T(n) = S(k) = \Theta(k \lg k)$. $T(n) = \Theta((\lg n) \lg(\lg n))$.

Conclusion on T(n) Recurrence Solution

The solution to the recurrence relation $T(n) = 2T(\sqrt{n}) + \lg(n)$ is $T(n) = \Theta(\lg(n) \lg(\lg(n)))$. This means the asymptotic time complexity is $O(\lg(n) \lg(\lg(n)))$.

Revision Table: Recurrence Relation Solution Steps

Additional Information: Recurrence Solving Techniques

Solving recurrence relations is fundamental in analyzing the time complexity of recursive algorithms. While the Master Theorem is very useful, it doesn't cover all types of recurrences. For recurrences like $T(n) = 2T(\sqrt{n}) + \lg(n)$, a change of variables is a key technique to transform it into a solvable form.

The Master Theorem simplifies the process for recurrences of the form $T(n) = aT(n/b) + f(n)$.

• If recursive cost dominates ($f(n)$ is relatively small), complexity is $O(n^{\log_b a})$.
• If costs are balanced, complexity is $O(n^{\log_b a} \log n)$.
• If the cost of the non-recursive part dominates ($f(n)$ is relatively large), complexity is $O(f(n))$.

In our specific case, the change of variables yielded a balanced case where the cost per level is roughly the same as the work done at the top level in the recursive tree representation (after transformation).

Another method for solving recurrences is the iteration method (or recursion tree method), where you expand the recurrence for a few levels to find a pattern and then sum up the costs. This method can be more general but is often more complex algebraically than the Master Theorem or a suitable change of variables.