Again, all three of these questions were easy, but were marked. So, alas, I'll put their solutions here too.
4.3-1[clrs]:
This can be done only if $c+n \leq 2cn$. Now, assume, $c \geq 1$ and $n \geq 1$, then $c+n \geq 2$ and $2cn \geq 2$. Therefore this inequality can exist for these assumptions.
4.3-2[clrs]:
Note that this inequality will only exist if $log(\frac{n}{2}+1) \leq log(\frac {n}{2})+1$. It's proof(backwards):
Raising both sides to the power of 2.
$$\frac{n}{2}+1 \leq 2^{log(\frac{n}{2})+1}\\ \frac{n}{2}+1 \leq 2 \times 2 ^{log \frac{n}{2}}\\ \frac{n}{2}+1 \leq 2 \times \frac{n}{2} \\ \frac{n}{2}+1 \leq n \\ 1 \leq \frac{n}{2} \\ 2 \leq n$$
Therefore, $n_0 = 2$, for our inequality to exist.
4.3-3[clrs]:
Notice that here too we are needed to prove that $log(\frac{n}{2})-1 \leq log(\frac{n}{2}-1)$, but that can easily be derived from the proof we did in the last answer, by putting $\frac{n}{2}-1$ in place of $\frac{n}{2}$.
4.3-1[clrs]:
Show that the solution of $T(n)=T(n-1)+n$ is $O(n^2)$.Assume $T(n) \leq cn^2$, for some constant $c$. Then we'll have, $$T(n)\leq c(n-1)^2+n \\ =c(n^2+1-2n)+n\\=cn^2+c-2cn+n\\ \leq cn^2$$
This can be done only if $c+n \leq 2cn$. Now, assume, $c \geq 1$ and $n \geq 1$, then $c+n \geq 2$ and $2cn \geq 2$. Therefore this inequality can exist for these assumptions.
4.3-2[clrs]:
Show that the solution of $Tn(n)=T(\lceil n/2 \rceil)+1$ is $O(log n)$.Assume $T(n) \leq clog n-d$, for some constant $c$. Then we'll have, $$T(n) \leq c log(\lceil n/2 \rceil) -d+1 \\ = c log(\frac{n}{2}+1)-d+1 \\ < c(log(\frac{n}{2})+1)-d+1 \\ = c(logn - log2+1)-d+1 \\= clog n -d +1 \\ \leq clogn$$
Note that this inequality will only exist if $log(\frac{n}{2}+1) \leq log(\frac {n}{2})+1$. It's proof(backwards):
Raising both sides to the power of 2.
$$\frac{n}{2}+1 \leq 2^{log(\frac{n}{2})+1}\\ \frac{n}{2}+1 \leq 2 \times 2 ^{log \frac{n}{2}}\\ \frac{n}{2}+1 \leq 2 \times \frac{n}{2} \\ \frac{n}{2}+1 \leq n \\ 1 \leq \frac{n}{2} \\ 2 \leq n$$
Therefore, $n_0 = 2$, for our inequality to exist.
4.3-3[clrs]:
We saw that the solution of $T(n)=2T(\lfloor n/2 \rfloor)+n$ is $O(nlogn)$ . Show that the solution of this recurrence is also $\Omega (n logn )$. Conclude that the solution is $\Theta (n logn )$.Assume, this time that $T(n) \geq c logn $ for some constant $c$. Then we'll have, $$ T(n) \geq 2 c \lfloor \frac {n}{2} \rfloor log \lfloor \frac{n}{2} \rfloor +n \\ T(n) \geq 2(c(\frac{n}{2}-1)log(\frac{n}{2}-1))+n \\ T(n) \geq 2 (\frac {cn}{2}-c)log(\frac{n}{2}-1)+n\\2(\frac{cn}{2}-c)(log(\frac{n}{2})-1)+n \\ T(n) \geq (cn -2c)(log(\frac{n}{2})-1 )+n \\ T(n) \geq (cn-2c)(log n -2) +n \\ T(n) \geq cnlogn -2cn -2clogn + 4c +n\\ T(n) \geq cnlogn$$
Notice that here too we are needed to prove that $log(\frac{n}{2})-1 \leq log(\frac{n}{2}-1)$, but that can easily be derived from the proof we did in the last answer, by putting $\frac{n}{2}-1$ in place of $\frac{n}{2}$.
No comments:
Post a Comment