# Tag Info

## New answers tagged recurrence-relation

1

Your recurrence isn't really defined for $n = 1$. This suggests using a different value for the lower bound in the integral. The formula given by Akra–Bazzi doesn't actually depend on the exact value of the lower bound that you choose – it can at most affect the big Theta constant or, in your case, some lower order term. If you choose any lower bound which ...

1

The guess $O(n^2)$ also works: $$T(n) \leq 2c\lfloor n/2\rfloor^2 + n \leq \frac{c}{2} n^2 + n \leq cn^2,$$ as long as $c \geq 2$. The author did not guess the answer. Presumably the author already knew the answer. In practice, for most recurrences you would encounter one of the following methods will work: Open up the recurrence (also known as ...

2

To guess simple recurrences most useful step is to study basic intuition beyond so-called master theorem that looks at any recursion as if it is implicit tree. Your case is admissible for it and thus easy: on each step you have half of task (peek one branch down in tree), and $O(n)$ work. Multiply tree height and amount of work on each step and you will get ...

1

The transformation: You define $S(m) = T(2^m)$ which is absolutely fine. $T(m) = T(m^{1/2}) + m$, so $T(2^m) = T(2^{m/2}) + 2^m$. Therefore $S(m) = T(2^m) = T(2^{m/2}) + 2^m = S(m/2) + 2^m$. That's the mistake you made, the last term is $2^m$ and not $m$. Try $n = 2^{1024}$: $T(2^{1024}) = T(2^{512}) + 2^{1024} = T(2^{256}) + 2^{512} + 2^{1024}$ and ...

-4

Complexity of above recurrence is O(m) which is O(log m) and now n = 2 ^m so m = log n and hence complexity is O(log log n).

2

You can solve this using the master theorem, whose proof uses a recursion tree argument. Define $S(n) = T(2^n)$. The main observation is that $\sqrt[3]{2^n} = 2^{n/3}$, and so $$S(n) = 9S(n/3) + O(1).$$ The solution is $S(n) = \Theta(n^2)$, and so $$T(n) = S(\log n) = \Theta(\log^2 n).$$ You can also open the recurrence directly, obtaining  T(n) \...

Top 50 recent answers are included