0

$T(n) = T(\log (n)) + O(\log(\log (n)))$

assuming $n =2 \ ^ {m}$ for $m \in N $

I need to prove by induction an upper bound.

I thought of doing the following:

$$T(2\ ^{m} )= T(m) + O(log(m)) $$

define $S(m) := T(2 \ ^ {m}) $ we get : $$S(m) = S(log(m)) + O(log(m)) $$

I'm not sure how to continue.

Did
  • 279,727
  • Define $(x_k)$ recursively by $x_{k+1}=e^{x_k}$ for every $k$, for some given $x_0$, then $T(x_k)=T(x_{k-1})+O(x_{k-2})$ hence $T(x_k)=O(y_k)$ with $y_k=x_{k-2}+x_{k-3}+\cdots+x_0$. Now, $e^x\geqslant2x$ for every nonnegative $x$ hence $x_i\leqslant\frac12x_{i+1}$ for every $i$ and $y_k\leqslant2x_{k-2}$. Finally, $T(x_k)=O(x_{k-2})$ and $x_{k-2}=\log\log x_k$, and I guess you are supposed to deduce from all this that $T(n)=O(\log\log n)$ although the implication does not hold. – Did Nov 16 '16 at 17:11

1 Answers1

0

You don't have upper bound cos $T(2^m)-T(m)\ge t>0$ since you can continue doing infinite times $T(2^{2^{.^{.^{.^m}}}})$ and each next is for a non infinitely small number bigger then previous.

Djura Marinkov
  • 2,595
  • $n=2 \ ^ m $ , did you consider that in your answer? Because this question has an upper bound, I didn't got to it yet.. –  Nov 16 '16 at 11:31
  • @Liad So if $n=2^m$ $T(n)=T(m)+...$ but then again $T(m)=T(\log m)+...$ and so on... Eventually you will need $\log(\log(log...(\log n)...))$ but it won't be defined – Djura Marinkov Nov 16 '16 at 11:39
  • For each n T(n) is defined so i dont see a problem , it is a question from an Algorithms course so you may consider it is legal –  Nov 16 '16 at 11:44
  • @Liad Ok, my fault – Djura Marinkov Nov 16 '16 at 12:30