# Tag Info

0

You want to prove a tight $\Theta(n)$ bound as @vonbrand commented you could to show: $$am+b \leq T(m)\leq cm+d\quad (1)$$ Now start by assuming $(1)$ holds for all $m < n$ and conclude: $$T(n) = 2T(n/3+1)+n \geq 2(a(n/3+1)+b)+n \geq n(2/3a+1) + 2(a+b)$$ $$T(n) = 2T(n/3+1)+n \leq 2(c(n/3+1)+d)+n \leq n(2/3c+1) + 2(c+d)$$ Thus $an+b \leq T(n)\leq cn+d$. ...

2

The definition of $\lceil x \rceil$ is: $\lceil x \rceil$ is the minimal integer $n$ such that $n \geq x$. (The existence of such an integer makes the reals an Archimedean field.) Let us assume, for the sake of contradiction, that $\lceil x \rceil \geq x + 1$. Then $\lceil x \rceil - 1 \geq x$. Since $\lceil x \rceil - 1$ is also an integer, this ...

2

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 ...

Top 50 recent answers are included