0
$\begingroup$

This question already has an answer here:

I really need help to solve the following: T(n)=T(n-a)+n where a is a constant greather or equal 1.

So I started to iterate T(n)=T(n-a)+n =T(((n-a)+n)-a)+n =T(3n-3a)+n =T(((3n-3a)+n)-a)+n =T(4n-4a)+n

this brings me to the Basic: T(kn-ka)+n.

Is it right ? I am not sure how to solve such Terms with a constant ? thank you for your help !!

$\endgroup$

marked as duplicate by D.W., Yuval Filmus, FrankW, David Richerby, Luke Mathieson Nov 14 '14 at 4:04

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

0
$\begingroup$

Hint: Let's solve the case $a = 1$; I'll leave the generalization to you: $$ \begin{align*} T(n) &= n + T(n-1) \\ &= n + (n-1) + T(n-2) \\ &= n + (n-1) + (n-2) + T(n-3) \\ &= \cdots \\ &= n + (n-1) + (n-2) + \cdots + (1) + T(0) \\ &= \frac{n(n+1)}{2} + T(0). \end{align*} $$ In the general case, if $n = ma$ then you'll get $am(m+1)/2 + T(0) \approx n^2/(2a) + T(0)$.

$\endgroup$
  • $\begingroup$ Hi! First of all thanks for your Response! :) I solved the case when a = 1 but due to the reason that a can be 2, 3 ... I don´t think that it is right ? My solution for the case that a = 1 Looks like: $\endgroup$ – bee23 Nov 12 '14 at 21:50
  • $\begingroup$ T(n) = T(n-1) + n / (n-1) It step T(n-1) = T(n-2) + (n-1) / (n-2) It step T(n-2) = T(n-3) + (n-2) --> T(n) = T(n-2) + (n-1) + n T(n) = T(n-3) + (n-2) + (n-1) + n The base = T(k-a) + kn - 1/2(k(k-1)) $\endgroup$ – bee23 Nov 12 '14 at 21:57
  • $\begingroup$ The same method works for any constant $a$. Keep trying and you'll get my formula eventually. You can even get a formula when $n$ is not a multiple of $a$. $\endgroup$ – Yuval Filmus Nov 12 '14 at 22:00
0
$\begingroup$

Okay :) let´s try again.

T(n) = T(n – a) + n / a=1

  1. T(n) = T(n-1) + n /Iterationstep
  2. T(n-1) = T(n-2) + (n-1) / (n-2) Iterationstep
  3. T(n-2) = T(n-3) + (n-2)

-> T(n-1), T(n-2) in T(n):

T(n) = T(n-2) + (n-1) + n

T(n) = T(n-3) + (n-2) + (n-1) + n

Base= T(k-a) + kn – ½(k(k-1))

n - k =1 --> T(1)

T(n) = T(1) + (n-1)n - (n-1)(n-2)/2

(n(n+1))/2= Ω (n2)

So this is my solution for a = 1 I think/hope it is right ?!

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.