0
$\begingroup$

Given $i < n/2$ and denoting $[x]$ to be an integer part of $x$ (floor$(x)$) and $(a \operatorname{rem} b)$ to be a reminder when $a$ is divided by $b$.

$$ T(n,i) = \left(\left\lfloor\frac{n-i}{i}\right\rfloor \cdot i\right) + T\left(i + (n \operatorname{rem} i), (n \operatorname{rem} i)\right) $$ then is $T(n,i) = O(n)$?

  • 1
    What is $T(n, 0)$?2012-08-30
  • 0
    T(n,0) = 0 and T(n,1) = n2012-08-30
  • 0
    I'm not sure if the following makes any sense or even correct. Anyways it might help you towards a correct answer. Fix an $i < n/2$. Then we have $\lfloor \frac{n-i}{i} \rfloor < n-1$, and $n \bmod i < i-1$. Hence $T(n, i) <$ $(n-1) +$ $T(2i-1, i-1)$. If $i$ is fixed to a constant, then $T(n, i) < n-1,$ hence $T(n, i)$ $\in$ $\mathcal{O}(n)$. Continuing on this gibberish, if $i$ is not constant: we actually have $T(n, i)$ $<$ $(n-1)$ $+ (n-2)$ $+ \cdots +$ $(n-i)$ $\in$ $\mathcal{O}(ni - i^2)$ $\in$ $\mathcal{O}(n^2)$.2012-08-30
  • 0
    Proceeding on the lines of analysis for Euclid's GCD algorithm we can actually say T(n,i) = O(nLogn). I want to know if we can better analyse the sum and actually say it is O(n) or not.2012-08-31

1 Answers 1

0

First, rewrite it a bit: $rem \to mod$. $\left\lfloor\frac{n-i}{i}\right\rfloor=\left\lfloor\frac{n}{i}-1\right\rfloor=\left\lfloor\frac{n}{i}\right\rfloor-1$

$$T(n,i) = \left(\left\lfloor\frac{n}{i}\right\rfloor-1\right)i + T\left(i +(n\operatorname{mod}i), (n \operatorname{mod} i)\right)$$

Consider $n=ki+l$, where $k-$non-negative integer, $l-$integer such that $0\le l

Then, $$ T(n,i)= (k-1)i+T(i+l,l)=n-l-i+T(i+l,l) $$ Now, consider $i=ml+h$, where $m-$non-negative integer, $h-$integer, $0\le h

Then, $$ T(i+l,l)=ml+T(l+h,h)=i-h+T(l+h,h) $$ So, we've got repetitive pattern, which ends when we encouter $T(x,1)$ or $T(x,0)$.

Let us denote $i=a_0$, $l=a_1$, $h=a_2$ and so on, where general term is $a_{p+1}=a_{p-1}\operatorname{mod}a_p$, then $$ \begin{align*} T(n,i) &= n-a_0-a_1+T(a_0+a_1,a_1)=\\ &= n-a_1-a_2+T(a_1+a_2,a_2)=\\ &= n-a_2-a_3+T(a_2+a_3,a_3)=\\ &= \dots =\\ &= n-a_{p-1}-a_p+T(a_{p-1}+a_p,a_p) \end{align*} $$ Hence, in case of $\color{red}{a_p=1}\to T(a_{p-1}+a_p,a_p)=a_{p-1}+a_p$

$$ \color{red}{T(n,i)=n} $$ In case of $\color{red}{a_p=0}\to T(a_{p-1}+a_p,a_p)=0$ $$ \color{red}{T(n,i)=n-a_{p-1}\to O(n)} $$ Notice, that in last case $2\le a_{p-1}

Thus, we can combine both cases $$ \color{red}{T(n,i)\to O(n),\quad C\in[1/2,1]} $$ where $C$ is a constant hidden behind $O(n)$.