# Tag Info

### 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 ...
• 39.1k
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,585
Accepted

• 4,511

### 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,611

### 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,046
Accepted

### Meaning of polynomially larger or smaller in the context of the master method

(This answer refers to the version 6 of the question, which does not contain "my professor's response".) It looks like there is some typo/inconsistency/misunderstanding somewhere in your ...
• 39.1k
Accepted

### Formulating the master theorem with Little-O- and Little-Omega notation

I am wondering if this means that we can write this first case of the theorem as $f \in o(n^{\log_b{a}})$ (and following the same logic, $f \in \omega(n^{\log_b{a}})$ for the third case), rather than ...
• 39.1k

• 278k
Accepted

### Justifying a claim in the proof of the master theorem

Suppose that $f(n) = O(n^{\log_b a - \epsilon})$. According to the definition, there exist constants $N,C>0$ such that $f(n) \leq Cn^{\log_b a - \epsilon}$ for all $n \geq N$. Let $M$ be the ...
• 278k
Accepted

### How can we get upper bound in terms of Big Oh notation using Master theorem?

Your reasoning is wrong. It is in $\Theta(n^{\log_2(5)})$. Hence, it is also in $O(n^{\log_2(5)})$. Answer to the update: Also, for the update part, it is wrong. You can find it by a straightforward ...
• 3,582
Let's take the slightly more general case where $a=b$ and $f(n)=n\;log\;n$ (in your case, $a=b=3$). Assume the usual restrictions on $a$ and $b$ hold. Then $n^{log_ba}=n$. This might lead us to ...