3

I have the following recursive function(an example from a textbook):

$$ T(n)=\begin{cases}1&n=1\\T(\lfloor\tfrac n2\rfloor)+T(\lceil\tfrac n2\rceil)+1&n>1\end{cases} $$

A recursion is used in order to prove that $T(n) = O(n)$

The hypothesis is: for each $k$ such that $\lfloor\tfrac n2\rfloor\leq k\leq n-1$ we get: $T(k)\leq c\cdot k$

My Question: why did they take a region of $k$ rather than a single value of $k$, I mean why not say: for $k = \lfloor\tfrac n2\rfloor$ we get that $T(k)\leq c\cdot k$

String
  • 18,395
ThunderWiring
  • 141
  • The use of the terms lower bound and upper bound seems a bit confusing to me. Do you mean floor function and ceiling function so that it is $$T(n)=\begin{cases}1&n=1\T(\lfloor\tfrac n2\rfloor)+T(\lceil\tfrac n2\rceil)+1&n>1\end{cases}$$ – String Apr 02 '15 at 08:41
  • @String, yes exactly. i didn't know how to show it in the picture. excuse my humble skills, im still new member here :) – ThunderWiring Apr 02 '15 at 08:47
  • I formatted it for you - you can edit your post or right click on math expressions to see the $\TeX$-commands that I used. I hope my edit is OK!? – String Apr 02 '15 at 09:00
  • yes it's alright, thank you. – ThunderWiring Apr 02 '15 at 09:01

0 Answers0