Tag Info

Solving a recurrence relation with √n as parameter

In your comment you mentioned that you tried substitution but got stuck. Here's a derivation that works. The motivation is that we'd like to get rid of the $\sqrt{n}$ multiplier on the right hand side,...
• 14.6k

How to solve T(n)=2T(√n)+log n with the master theorem?

Let us actually use the master theorem. Define $S(n) = T(e^n)$ for all $n$. Then $$S(n) = T(e^n) = 2T(\sqrt{e^n}) + \log(e^n) = 2T(e^{n/2}) + n = 2S(n/2) + n$$ Now we can apply the second case of ...
• 34.9k
Accepted

Solving recurrence relation with square root

The answer cannot be $O(\log\log n)$. Already without applying any recursion we have the inequality $T(n) = T(\sqrt{n}) + n \ge n$. So the complexity cannot be smaller than $O(n)$. But now to your ...
• 1,336
Accepted

Master Method to solve recurrences is 'a' related to 'b'?

No it's not always the case that $a=b$, since you might not necessarily use every sub-problem. Consider for example, the binary search algorithm. In the algorithm, you have a sorted array that you ...
• 1,103
Accepted

• 4,371

What is the recurrence form of Bubble-Sort

Bubble sort uses the so-called "decrease-by-one" technique, a kind of divide-and-conquer. Its recurrence can be written as $$T(n) = T(n-1) + (n-1).$$
• 9,219

How to solve T(n)=2T(√n)+log n with the master theorem?

As discussed in the other answer, the Master Theorem does not apply here. To solve this recurrence, we can follow the similar steps in Solving recurrence relation with square root. For $n=2^m$, we ...
• 1,016

How to use Master Theorem with strange format of $b$ parameter?

Not every recurrence falls within the bounds on the master theorem. Your recurrence is an example. However, by unrolling your recurrence, we can come up with an explicit formula:  T(n) = 6(n+1) + T(...
• 270k