1
$\begingroup$

I have $T:$ $\mathbb{N} \rightarrow \mathbb{N}$

Such that $T(1)=1$, $T(n)=T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil)$ for all $n\ge2$.

My work:

If $n$ is even then $\lceil n/2 \rceil = \lfloor n/2 \rfloor=n/2$.

If $n$ is odd, then we have $\lceil n/2 \rceil -1 = \lfloor n/2 \rfloor=(n-1)/2$.

Using the above results, we have \begin{eqnarray*} T(n)&=&2T(n/2)&\quad\text{ if n is even, }\\ T(n)&=& T((n-1)/2)+ T((n+1)/2)&\quad\text{ if n is odd.} \end{eqnarray*} I conjecture that $T(n)=n$ for all n.

I proved the base case for $n=2$ and then assumed that the formula is true for $n=k$. Now I will try to prove that it is also true for $n=k+1$.

I know that $k+1$ can either be odd or even, so I have to consider both possibilities, but i'm not sure how to proceed here. I appreciate any help

$\endgroup$
  • $\begingroup$ Your definition of $T(n)$ seems to be missing some parentheses, and maybe a $T$? I have attempted to fix it, let me know if I understood correctly. $\endgroup$ – Inactive - Objecting Extremism Mar 5 at 1:08
  • $\begingroup$ @Servaes please wait for a response before changing the meaning of their math. $\endgroup$ – The Great Duck Mar 5 at 1:09
  • $\begingroup$ @TheGreatDuck The math was syntactically incorrect, and the rest of the question strongly suggested this was the intended meaning. And your edit wasn't a rollback, so don't call it that. $\endgroup$ – Inactive - Objecting Extremism Mar 5 at 1:10
  • 1
    $\begingroup$ @Servaes Your edit is correct. Thanks! $\endgroup$ – user140161 Mar 5 at 1:13
  • $\begingroup$ @Servaes Yes, it was a rollback. I removed your edit. $\endgroup$ – The Great Duck Mar 6 at 0:42
1
$\begingroup$

By induction $T(N)=N$; the base case $N=1$ holds by definition.

Suppose $T(n)=n$ for all $n<N$. Then if $N$ is even $$T(N)=T(\lfloor\tfrac{N}{2}\rfloor)+T(\lceil\tfrac{N}{2}\rceil)=T(\tfrac{N}{2})+T(\tfrac{N}{2})=\tfrac{N}{2}+\tfrac{N}{2}=N,$$ and similarly, if $N$ is odd, $$T(N)=T(\lfloor\tfrac{N}{2}\rfloor)+T(\lceil\tfrac{N}{2}\rceil)=T(\tfrac{N-1}{2})+T(\tfrac{N+1}{2})=\tfrac{N-1}{2}+\tfrac{N+1}{2}=N.$$ By induction $T(N)=N$ for all $N\in\Bbb{N}$.

$\endgroup$
  • 1
    $\begingroup$ Beware, we need to have $\dfrac{N+1}2<N\iff N>1\iff N\ge 2$ for the induction to be not self-referencing. So $T(2)$ should also be verified as initial step. $\endgroup$ – zwim Mar 5 at 1:13
  • 1
    $\begingroup$ @zwim You are right that this proof of the induction step is only valid for $N\geq2$. But $T(2)$ need not be verified because the base case $N=1$ has already been verified, so the first application of the induction step is with $N=2$. $\endgroup$ – Inactive - Objecting Extremism Mar 5 at 1:22
0
$\begingroup$

Definitely $T(n)=n$ is a solution $$ T\left( n \right) = n = T\left( {\left\lfloor {n/2} \right\rfloor } \right) + \left\lceil {n/2} \right\rceil $$ because $$ n = \left\lfloor {n/2} \right\rfloor + \left\lceil {n/2} \right\rceil \quad \left| {\;\forall n \in \mathbb Z} \right. $$ and $$ T\left( 1 \right) = 1 $$

$\endgroup$

Your Answer

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

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