New answers tagged

1

I eventually found the solution for the first problem I proposed. Lemma 10.5.3.2 CAN be proved by induction, but it requires additional lemmata for doing so. I was misled by the note on page 292, specifically by the mention of "strengthening". It is common to say that a theorem is strengthened when its inductive hypothesis is rewritten to hold in ...


2

Your counter-example isn't true. Let $f(n)=2^n$, we see that $$f(\frac{n}{2})=2^\frac{n}{2}=\sqrt{2}^n.$$ As a result we show that $f(n)\neq\Theta(f(\frac{n}{2}))$ $$\lim_{n\to \infty}\frac{f(n)}{f(\frac{n}{2})}=\frac{2^n}{\sqrt{2}^n}$$ $$=\frac{2}{\sqrt{2}}\times\dots\times\frac{2}{\sqrt{2}}$$ $$=\frac{\sqrt{2}}{1}\times\dots\times\frac{\sqrt{2}}{1}$$ $$=\...


Top 50 recent answers are included