0
$\begingroup$

I have the following complexity equation: $T(n)=T(n-i)+T(n-(\frac{n}{m}-i))$ with the base case $T(m)=1$.

Is it possible to calculate a big $O$ approximation for such equation? What is the right method to do so?

Edit: I actually need to calculate this equation for any $1\leq{i}<\frac{n}{m}$ so if it is easier to consider $i$ as a constant, such a solution is also helpful.

Edit 2: I think the equation is also missing floor value of $\frac{n}{m}$ so it will be coherent

Improve this question
$\endgroup$
  • $\begingroup$ I think $i$ should be between $1$ and $\frac{n}{m}$. Or at least $n-m$ should be less than $\frac{n}{m}$. Right? $\endgroup$ – OmG Jun 24 '20 at 12:56
  • $\begingroup$ yes, thanks for the correction I'll edit the main post $\endgroup$ – Ofir Gordon Jun 24 '20 at 13:23
  • $\begingroup$ Thank you. One more thing. Is $m$ constant? As you have mentioned that $T(m) = 1$. $\endgroup$ – OmG Jun 24 '20 at 13:40
  • $\begingroup$ Is it not required that $i<{n\over m}$ for all n, so $n-{n\over m} + i<n$ would hold for all n? It would directly imply that $i=1$. I suppose you have meant something else - maybe $i$ depends on $n$? then write it at $i_n$ for clarification. $\endgroup$ – nir shahar Jun 24 '20 at 14:13
  • $\begingroup$ @OmG yes let's consider $m$ as a constant. Does that mean the result wouldn't be dependent on $m$? $\endgroup$ – Ofir Gordon Jun 24 '20 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.