0

I'm stuck on trying to prove that

$ T(n)= T(n-2)+k$ is bounded by $O(n)$ for all $n >1$

I expanded it out to reach the following guess: $T(n) = ((n-2)/2)k $

though when I try to prove inductively, I get:

Base case : $T(2) = 0$

which is obviously incorrect. Any help would be greatly appreciated.

user2789945
  • 153

2 Answers2

1

The is no relation between $T(m), T(n)$ for $m$ even and $n$ odd.

For $m = 1, 2, \cdots$, we have $T(2m - 1) =T(1) + k(m - 1) , T(2m)=T(2)+k(m-1)$.

Explicitly, for $K > \max\{T(1),T(2)/2,k/2\}$, we have $$T(x)<Kx$$, because $$T(x)=T(2m-1)=T(1)+k(m-1)<K+2K(m-1)=K(2m-1)=Kx$$ and $$T(x)=T(2m)=T(2)+k(m-1)<2K+2K(m-1)=K(2m)=Kx$$.

Colliot
  • 864
  • Thank you for taking the time to answer, but I don't think I understand much of this at all. I was looking more for an answer similar to the other one posted, unfortunately. – user2789945 Apr 20 '15 at 07:25
  • @user2789945, where don't you understand? That answer is essentially contained in mine. – Colliot Apr 20 '15 at 07:28
  • @user2789945, I'm just proving that it is $O(n)$. Does't being $O(n)$ mean there is a constant such that $f(n) \le Kn$? – Colliot Apr 20 '15 at 07:29
  • That is true, yes. I'm actually understanding it now, I was initially confused because I haven't seen notation quite like this yet. – user2789945 Apr 20 '15 at 07:33
1

Actually, you need an initial value for $n=0$ and $n=1$, if you want to find the explicit formula for $T(n)$. Since you're asked to prove the solution is bounded, you may express the formula based on value of $T(0)$ and $T(1)$, and consider them as constants.

Anyway, if I'm not making a mistake $T(n) = T(0) + \dfrac{n}{2}k$ if $n$ is even and $T(n) =T(1) + \left \lfloor \dfrac{n}{2} \right \rfloor k$ if $n$ is odd. Then it is not difficult to check that the solution is $O(n)$.

Sorombo
  • 663
  • Yes, the initial values are also two different constants, which makes sense given the context of your answer (the actual problem deals with an implementation of the partition procedure on mergesort). – user2789945 Apr 20 '15 at 07:21