Skip to main content
added 284 characters in body
Source Link
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

Let's start with the issue of iteration. Suppose that a function $f$ satisfies $$ f(n/b) \leq (c/a)f(n). $$ Then it also satisfies $$ f(n/b^2) \leq (c/a)f(n/b) \leq (c/a)^2 f(n). $$ You can prove by induction that for all integer $t \geq 0$, $$ f(n/b^t) \leq (c/a)^t f(n). $$

As for your second question, about assuming that $n$ is large enough: you aren't really giving enough details to answer it. We'll have to check the entire proof is just sloppy.

Note You cannot assume that the premise does not imply that the regularity condition$f(n/b) \leq (c/a) f(n)$ holds for all $n \geq b$; it only states that there exists some. Indeed, in Introduction to Algorithms, third edition, they do not make such an assumption for the case where $n_0$$n$ is a power of $b$.

They do seem to make such as assumption in the case of general $n$, but what they are really saying is that the inequality $f(n/b) \leq (c/a) f(n)$$f(\lceil n/b \rceil) \leq (c/a) f(n)$ only makes sense for all $n \geq n_0$$n \ge b + b/(b-1)$. The assumption $n \neq b$ does not "satisfy"Using the condition thatidea of the proof of the special case where $n$ be large enough. This is because we're not trying to show thata power of $b$, you can complete the premise holdproof of the general case. RatherI would, we assume that it doeshowever, strongly suggest ignoring such technicalities at present. The master theorem is essentially a calculation, and try to make use ofyou can trust the authors that it works out. Nothing interesting is hidden under the rug.

Let's start with the issue of iteration. Suppose that a function $f$ satisfies $$ f(n/b) \leq (c/a)f(n). $$ Then it also satisfies $$ f(n/b^2) \leq (c/a)f(n/b) \leq (c/a)^2 f(n). $$ You can prove by induction that for all integer $t \geq 0$, $$ f(n/b^t) \leq (c/a)^t f(n). $$

As for your second question, about assuming that $n$ is large enough: you aren't really giving enough details to answer it. We'll have to check the entire proof.

Note that the premise does not imply that the regularity condition holds for all $n \geq b$; it only states that there exists some $n_0$ such that $f(n/b) \leq (c/a) f(n)$ for all $n \geq n_0$. The assumption $n \neq b$ does not "satisfy" the condition that $n$ be large enough. This is because we're not trying to show that the premise hold. Rather, we assume that it does and try to make use of it.

Let's start with the issue of iteration. Suppose that a function $f$ satisfies $$ f(n/b) \leq (c/a)f(n). $$ Then it also satisfies $$ f(n/b^2) \leq (c/a)f(n/b) \leq (c/a)^2 f(n). $$ You can prove by induction that for all integer $t \geq 0$, $$ f(n/b^t) \leq (c/a)^t f(n). $$

As for your second question, about assuming that $n$ is large enough: the proof is just sloppy. You cannot assume that $f(n/b) \leq (c/a) f(n)$ holds for all $n \geq b$. Indeed, in Introduction to Algorithms, third edition, they do not make such an assumption for the case where $n$ is a power of $b$.

They do seem to make such as assumption in the case of general $n$, but what they are really saying is that the inequality $f(\lceil n/b \rceil) \leq (c/a) f(n)$ only makes sense for $n \ge b + b/(b-1)$. Using the idea of the proof of the special case where $n$ is a power of $b$, you can complete the proof of the general case. I would, however, strongly suggest ignoring such technicalities at present. The master theorem is essentially a calculation, and you can trust the authors that it works out. Nothing interesting is hidden under the rug.

Source Link
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

Let's start with the issue of iteration. Suppose that a function $f$ satisfies $$ f(n/b) \leq (c/a)f(n). $$ Then it also satisfies $$ f(n/b^2) \leq (c/a)f(n/b) \leq (c/a)^2 f(n). $$ You can prove by induction that for all integer $t \geq 0$, $$ f(n/b^t) \leq (c/a)^t f(n). $$

As for your second question, about assuming that $n$ is large enough: you aren't really giving enough details to answer it. We'll have to check the entire proof.

Note that the premise does not imply that the regularity condition holds for all $n \geq b$; it only states that there exists some $n_0$ such that $f(n/b) \leq (c/a) f(n)$ for all $n \geq n_0$. The assumption $n \neq b$ does not "satisfy" the condition that $n$ be large enough. This is because we're not trying to show that the premise hold. Rather, we assume that it does and try to make use of it.