0

$$ \DeclareMathOperator{ceil}{ceil} T(n) = \begin{cases} 10 & \text{ if } n=1 \\ 7 \, T(\ceil(n/2)) + n^2 & \text{ if } n>1 \end{cases} $$ a) Use n to find positive real constants c,d such that T(n) <= c n^{lg base 2 7} - d n^2, for all n that are powers of 2

I'm having trouble understanding when to use my Induction Hypothesis:
BC: 10 <= c
IS: let n>= 1 Suppose f(n)<= c n^{lg base 2 7} - d n^2
f(n+1) = 7 T(ceil(n/2)) + n^2
<= 7 T(n+1) + n^2
which is where i want to use the IH, but it makes no sense to use the IH on f(n+1) because it defeats the purpose, however i dont know how else to deal with the ceil

mvw
  • 34,562
  • What does 'ceil' mean ? – Evargalo May 24 '17 at 13:08
  • ceiling, as in round up, ceil(1.5) = 2 –  May 24 '17 at 13:18
  • Ok, thanks. You seem to have an issue with your expression of f(n+1). Moreover, since you have to prove the formula for n powers of 2, you should not build $T(n+1)$ but $T(2n)$ in your IS... – Evargalo May 24 '17 at 13:28
  • Otherwise, the exercise seems a bit weird to me since ceil(n/2)=n/2 for all n powers of 2 but n=1. – Evargalo May 24 '17 at 13:30
  • we were instructed to use n, rather than 2n, and yea the exception of n=1 is a pain –  May 24 '17 at 13:41
  • Are you allowed to write $n=2^k$ and use an induction argument on $k$? And what exactly stop you from writing $T(n)=7T(n/2)+n^2$ if $n>1$ ? – Evargalo May 24 '17 at 13:47
  • i just tried using this with complete induction, i get to f(n) = 7c(n/2)^log2_7 - d(n/2)^2 +n^2, however im having trouble connecting it to be <= cn^log2_7 - dn^2 –  May 24 '17 at 13:51
  • Did you mean $T(n) \le c;n^{log_2 7} + d;n^2$ instead of $T(n) \le c;n^{log_2 7} - d;n^2$? – user137481 May 26 '17 at 17:22

0 Answers0