Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
What is $T(n, 0)$? – user2468 Aug 30 '12 at 21:14
T(n,0) = 0 and T(n,1) = n – rTeja Aug 30 '12 at 21:17
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)$. – user2468 Aug 30 '12 at 22:10
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. – rTeja Aug 31 '12 at 3:33

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.