0
$\begingroup$

Assume this recurrence: $$T(n)=T(n-2)+\frac{1}{\lg{n}}$$ I tried to draw its recurrence tree and I reached that the whole cost is $\dfrac{1}{\lg{n}}+\dfrac{1}{\lg{n-2}}+\dots+\dfrac{1}{x}$ that $x$ is $2$ if $n$ is even, otherwise is $3$. So somehow we should solve $\sum_{i=1}^{\frac{n}{2}}{\dfrac{1}{\lg{2i}}}$ or $\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}{\dfrac{1}{\lg{2i+1}}}$ that both equal to the same $\Theta(f(n))$. I read somewhere that it equals $\Theta(\dfrac{n}{\lg{n}})$, but I can't find out how. The lower bound is easy, but what about the upper bound?

$\endgroup$

2 Answers 2

3
$\begingroup$

Ignoring rounding (which does not affect the asymptotic growth rate): $$ \sum_{i=1}^{n/2} \frac{1}{\log 2i} \ge \sum_{i=1}^{n/2} \frac{1}{\log n} \ge \frac{1}{2} \cdot \frac{n}{\log n} = \Omega\Big(\frac{n}{\log n}\Big), $$ and

$$ \begin{align*} \sum_{i=1}^{n/2} \frac{1}{\log 2i} &= \sum_{i=1}^{\sqrt{n}/2} \frac{1}{\log 2i} + \sum_{i=\sqrt{n}/2}^{n/2} \frac{1}{\log 2i} \le \sqrt{n} + \frac{n}{\log \sqrt{n}} \\ & = O(\sqrt{n}) + \frac{1}{2} \cdot \frac{n}{\log n} = O\Big(\frac{n}{\log n}\Big). \end{align*} $$

$\endgroup$
0
$\begingroup$

Every recursion formula of the form $T(n) = T(n-k) + f(n)$ for sum fixed $k$ can be turned into a sum: $T(n)$ is the sum of $f(n - i\times k)$ for those $i$ where $f(n - i\times k)$ is not known, plus the first known value. In your case you would need to know $T(1)$ and $T(0)$ without the recursion formula.

Note that for $\sqrt n ≤ j ≤ n$ we have $(\log j) / 2 ≤ \log j ≤ \log n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.