# Time Complexity of $T(n)=T(n-2)+\frac{1}{\log(n)}$

Solve $T(n)=T(n-2)+\frac{1}{\log(n)}$ for $T(n)$.

I am getting the answer as $O(n)$ by treating $1/\log(n)$ as $O(1)$. The recursive call tree of this is a lop-sided tree of height $n$. Hence, considering the amount of work done in each step, the answer comes out to be $O(n)$. Please verify my answer, and tell me if I am correct.

-

If $T(n)=T(n-2)+\frac{1}{\log(n)}$, then $$T(n)=\left\{\begin{array}{}T(0)+\sum_{k=1}^{n/2}\frac{1}{\log(2k)}&\text{if }n\text{ is even}\\T(1)+\sum_{k=1}^{(n-1)/2}\frac{1}{\log(2k+1)}&\text{if }n\text{ is odd}\end{array}\right.\tag{1}$$ Note that \begin{align} \sum_{k=1}^{(n-1)/2}\frac{1}{\log(2k+1)} &\le\frac{1}{\log(3)}+\int_1^{(n-1)/2}\frac{\mathrm{d}x}{\log(2x+1)}\\ &=\color{#C00000}{\frac{1}{\log(3)}+\frac12\int_3^8\frac{\mathrm{d}x}{\log(x)}}+\frac12\int_8^n\frac{\mathrm{d}x}{\log(x)}\tag{2} \end{align} and \begin{align} \sum_{k=1}^{n/2}\frac{1}{\log(2k)} &\le\frac{1}{\log(2)}+\int_1^{n/2}\frac{\mathrm{d}x}{\log(2x)}\\ &=\color{#C00000}{\frac{1}{\log(2)}+\frac12\int_2^8\frac{\mathrm{d}x}{\log(x)}}+\frac12\int_8^n\frac{\mathrm{d}x}{\log(x)}\tag{3} \end{align} For $n\ge8$, we have that $\log(x)\le2(\log(x)-1)$, thus \begin{align} \frac12\int_8^n\frac{\mathrm{d}x}{\log(x)} &\le\int_8^n\frac{(\log(x)-1)\mathrm{d}x}{\log(x)^2}\\ &=\frac{n}{\log(n)}\color{#C00000}{-\frac{8}{\log(8)}}\tag{4} \end{align} Combining $(1)$ though $(4)$, we get that $$T(n)\le\color{#C00000}{C}+\frac{n}{\log(n)}=O\left(\frac{n}{\log(n)}\right)\tag{5}$$

-
Excellent! this is really nice – pritam Jul 8 '12 at 9:03

$$T(n)=T(n-2)+1/\mbox{log }n=T(n-4)+1/\mbox{log }(n-2)+1/\mbox{log }n=\cdots$$ So $$T(n)=a+\sum_{i=1}^{\lfloor n/2\rfloor}\frac{1}{\mbox{log}(n-2i)}\leq a+\sum_{i=1}^{\lfloor n/2\rfloor}\frac{1}{b}=a+bn/2=O(n)$$ Where $a=T(0),T(1)$ and $b=\mbox{log }2,\mbox{log }3$ depending on even or odd $n$. This shows that O(n) is an upper bound

-

$T(n)=T(n-2)+\frac{1}{\log(n)}$

$\implies T(n-2)=T(n-4)+\frac{1}{log(n)}+\frac{1}{\log(n-2)}$

So, $T(n) = T(n-2r)+\sum_{0≤2s<2r}\frac{1}{\log(n-2s)}$

If $n$ is even, $2r\leq n-2$, $T(n) = T(2)+\sum_{0≤2s<n-2}\frac{1}{\log(n-2s)}$

If $n$ is even, $2r\leq n-1$, $T(n) = T(1)+\sum_{0≤2s<n-1}\frac{1}{\log(n-2s)}$

In either cases, $O(n) = \frac{n}{\log(n)}$

-
I don't think the bound is that tight. – user17794 Jul 6 '12 at 9:39
@lab bhattacharjee: Can you explain how did you get O(n/log n) from that sum ? – pritam Jul 6 '12 at 9:48
@Pritam, each term in the summation is $O(log(n))$. Now there are 1+$\frac{(n-2)}{2} =\frac{n}{2}$ or 1+ $\frac{(n-1)}{2}= \frac{n+1}{2}$ terms respectively. Don't they result in $\frac{n}{log(n)}$ ? – lab bhattacharjee Jul 8 '12 at 4:28
@labbhattacharjee: You mean each term of the summation is $O(1/log(n))$ ? Thats not correct, in fact all the terms in the summation are bigger than $O(1/log(n))$ – pritam Jul 8 '12 at 9:01