1

This is part of a homework assignment I'm having trouble with and would be thankful for a little hint.

Let $a>b>1,c>0 \in \mathbb{N}$ and $T: \mathbb{N} \to \mathbb{N}$ defined recursively by $T(1) \leq c, T(n) \leq aT(\frac{n}{b})+cn$ and it can be assumed that $n=b^k$.

Show $T(n) \leq c \frac{a}{a-b} n^{log_b(a)}$ by induction.

My solution attempt:

Induction start:

$T(b^0) = T(1) \leq c \leq c \frac{a}{a-b} 1^{log_b(a)}$ is true since for $a>b>1$ we have $\frac{a}{a-b} = 1 + \frac{b}{a-b} \geq 1$.

Induction assumption:

$T(b^k) \leq c \frac{a}{a-b} (b^k)^{log_b(a)} = c \frac{a}{a-b} a^k$

Induction step from $T(b^k)$ to $T(b^{k+1})$:

$T(b^{k+1}) \leq a T(b^k) + cb^{k+1} \leq a [c \frac{a}{a-b} a^k ] + cb^{k+1} = c \frac{a}{a-b} a^{k+1} + cb^{k+1}$

But that is $ \not \leq c \frac{a}{a-b} a^{k+1}$, which is the right side I'm aiming for. Where did I go wrong?

mafu
  • 537
  • Um the conditions $T(b^k) \le a T(b^{k-1}) +cb^k$ aren't a "definition". – fleablood Apr 14 '16 at 16:53
  • Counter example: T(n) = 0 if n=$b^k$ and T(n) =$ \lceil c \frac{a}{a-b} n^{log_b(a)} \rceil + 1$ if $n \ne b^k$. I strongly suspect you are not presenting all the information. – fleablood Apr 14 '16 at 17:08
  • @fleablood I've checked and that is actually all. If you're worried about the $\leq$, I believe it can be replaced by a $=$ just as well. The purpose of this task is just to show the upper bound for the function. – mafu Apr 14 '16 at 18:16
  • (edited the question to make the intention more clear) – mafu Apr 14 '16 at 18:46
  • Well, I wonder why they make it so complicated. If this condition only applies when n= $b^k$ why state it in terms of n. If they mean all n then the conditions only applying to $n = b^k$ make that impossible as my counter example shows. But if they only mean for powers of b why write about the log_b n or n/b? I seriously think there must be some assumed condition for $b^k < n < b^{k+1}$. For example, is the function increasing. Instead of "it can be assumed $n=b^k$" (no it bloody well can't!) should it be ... some intermediate condition? – fleablood Apr 14 '16 at 19:24
  • I'm not worried about the $\le$ than. I'm worried about the "It may be assumed $n = b^k$" If $T: \mathbb N \rightarrow \mathbb N$ it bloody well can NOT be assumed. And as you showed you can not eliminate the "cn" addend. You hypothetically could by some "tightening" with $T(n) \le blah$ for $b^k < n < b^{k+1}$ but we know absolutely nothing about $T(n)$ when $n \ne b^k$. T(n;$n \ne b^k$) could equal a googleplex factorial for all the information we are given. – fleablood Apr 14 '16 at 19:36
  • @fleablood You're really overthinking it. $T(n)$ is just a function describing the cost of working with $n$ items. As usual with the Master Theorem, an algorithm works by calling itself on subsets of its input, and just to make the math easier (this is an undergrad course and the task I quoted is worth 1 single point), we are allowed to assume that the input has a nice, easy size which is a power of $b$. – mafu Apr 14 '16 at 23:38
  • @fleablood If $T$ interpolates linearly or "rounding up" to the next power or does something else is not very interesting as long as what it does is not too unusual (and we are confident that being given) for the $\BigO$ order. – mafu Apr 14 '16 at 23:39
  • But from what you write I understand that what I stated in the question is correct, and there is no solution that fits the schema described above? Then it seems the quiz itself has an error >_< – mafu Apr 14 '16 at 23:42
  • I'm not saying it can't be solved but I don't see how. We only know that T: {b^k} -> N and that $T(b^k) \le aT(b^{k-1}) + cb^k$. We are being asked to prove $T(b^k) \le c\frac a{a-b} a^k$. Good luck. I don't see why the problem was expressed other wise. – fleablood Apr 15 '16 at 00:46
  • For reference, the problem was correct as stated. To solve it, a tighter bound should be proved in the induction than the obvious one I chose. – mafu Oct 01 '16 at 01:54

0 Answers0