3

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.

Gigili
  • 5,503
  • 8
  • 41
  • 62
Mohammad Moiez Gohar
  • 31

3 Answers3

2

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} $$

robjohn
  • 345,667
  • Excellent! this is really nice – pritam Jul 08 '12 at 09:03
  • Should not it be as shown below in eq 4. Notice the power 2 is on the whole log. $$ \begin{align} \frac12\int_8^n\frac{\mathrm{d}x}{\log(x)} &\le\int_8^n\frac{(\log(x)-1)\mathrm{d}x}{\log^2(x)}\ &=\frac{n}{\log(n)}\color{#C00000}{-\frac{8}{\log(8)}} \end{align} $$

    And if that is the case then the inequality is wrong. Also, I did not understand that how you arrived at this equation.

     – V K Jun 01 '20 at 04:51
  • @VK: I am not sure what you are claiming. Are you saying that you disagree with equation $(4)$, or that you think equation $(4)$ somehow invalidates the inequality? Which equation do you not see how I arrived at? You've simply copied equation $(4)$. – robjohn Jun 01 '20 at 11:59
  • I was saying that in eq 4 on the right hand side denominator, x is squared. But for the right hand side to result in n/log(n) after integration, instead of x being squared full log(x) term should be squared in denominator. – V K Jun 01 '20 at 12:12
  • @VK: No. $\log(x)^2=(\log(x))^2$ not $\log\left(x^2\right)$, which would actually be $2\log(x)$. Operator precedence dictates that the parentheses around the argument of a function go before the exponent $2$. – robjohn Jun 01 '20 at 12:16
  • Eq 3 implies that $ \int_1^{(n-1)/2}\frac{\mathrm{d}x}{\log(2x+1)} = \frac12\int_1^n\frac{\mathrm{d}x}{\log(x)} $. Same thing is there in eq 2. But I do not understand how. What about the extra terms which come in $\frac12\int_1^n\frac{\mathrm{d}x}{\log(x)} $ like $1/log(4)$. How will dividing the integral by 2 will help? – V K Jun 02 '20 at 05:01
  • Also if we break up the right hand side of the inequality in eq 4 we get:

    $\frac12\int_8^n\frac{\mathrm{d}x}{\log(x)} \le\int_8^n \frac{(1)}{\log(x)} -\frac{(1)}{\log(x)^2 }\mathrm{d}x$

    If we solve this inequality further we will get that[I ingnored the integrals, solving the term inside it]:

    $$ -\frac12 \frac{1}{\log(x)} \le -\frac{1}{\log(x)^2} \tag{a}$$ $$ \frac12 \frac{1}{\log(x)} \ge \frac{1}{\log(x)} \tag{b}$$

    which is not true. So, what is it that I am doing wrong here?

     – V K Jun 02 '20 at 05:01
  • In $(3)$: $\int_1^{(n-1)/2}\frac{\mathrm{d}x}{\log(2x+1)}=\frac12\int_{\color{#C00}{3}}^n\frac{\mathrm{d}x}{\log(x)}$; and in $(2)$: $\int_1^{n/2}\frac{\mathrm{d}x}{\log(2x)}=\frac12\int_{\color{#C00}{2}}^n\frac{\mathrm{d}x}{\log(x)}$. These are simply changes of variable. – robjohn Jun 03 '20 at 04:11
  • Don't break up the right side of $(4)$: $\int\frac{(\log(x)-1)\mathrm{d}x}{\log(x)^2}=\frac{x}{\log(x)}$. Just evaluate at the endpoints. – robjohn Jun 03 '20 at 04:12
0

$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)}$

Gigili
  • 5,503
  • 8
  • 41
  • 62
lab bhattacharjee
  • 274,582
  • I don't think the bound is that tight. –  Jul 06 '12 at 09:39
  • @lab bhattacharjee: Can you explain how did you get O(n/log n) from that sum ? – pritam Jul 06 '12 at 09:48
  • 1
    @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 08 '12 at 04:28
  • 2
    @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 08 '12 at 09:01
0

$$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

pritam
  • 10,157