Solutions_to_Introduction_to_Algorithm_3nd_Exercise

Solutions_to_Introduction_to_Algorithm_3nd_Exercise_3

本文主要是介绍Solutions_to_Introduction_to_Algorithm_3nd_Exercise_3，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

3.1-1 Let f(n) and g(n) be asymptotically nonnegative functions. Using the basic definition of Θ-notation, prove that max(f(n),g(n))=Θ(f(n)+g(n)).
　　Let f(n),g(n) be asymptotically nonnegative. Show that max(f(n),g(n)) = Θ(f(n)+g(n)). This means that there exists positive constants c1,c2 and n0 such that, 0<= c1(f(n)+g(n))<=max(f(n),g(n))<=c2(f(n)+g(n)), for all n>=n0.
　　Selecting c2=1 clearly shows the third inequality since the maximum must be smaller than the sum. c1 should be selected as 1/2 since the maximum is always greater than the weighted average of f(n) and g(n). Note tha significance of the "asymptotically nonnegative" assumption. The first inequality could be satisfied otherwise

3.1-2 Show that for any real constants a and b, where b>0, $\left ( n+a \right )^b = \Theta \left ( n^b \right )$

　　To show that $\left ( n+a \right )^b = \Theta \left ( n^b \right )$ , we want to find constants c1,c2,n0>0 such that $0\leqslant c_{1}n^{b}\leqslant\left ( n+a \right )^b \leqslant c_{2}n^{b} \, for \,all \, n\geqslant n_{0}$

　　Note that $n+a\leqslant n+\left | a \right |\leqslant 2n,when \, \left | a \right | \leqslant n,$ and $n+a\geq n-\left | a \right |\leqslant \frac{1}{2}n,when \, \left | a \right | \leqslant \frac{1}{2}n,$ Thus, $when \, n \geq 2\left | a \right | ,0 \leqslant \frac{1}{2}n \leqslant n+a \leqslant 2n,$ Since b>0, the inequality still holds when all parts are raised to the power b:

$0 \leqslant \left ( \frac{1}{2} n\right )^b \leqslant \left (n+a \right )^b \leqslant \left ( 2n\right )^b,$

$0 \leqslant \left ( \frac{1}{2} \right )^b n^b \leqslant \left (n+a \right )^b \leqslant 2^b \left ( n\right )^b.$

Thus, $c_{1}=\left( \frac{1}{2}\right )^b,c_{2}=2^b,and\, n_{0}=2 \left | a\right|$ satisfy the definition.

3.1-3 Explain why the statement, "The running time of algorithm A is at least $O\left (n^{2} \right )$ ," is meaningless.

　　Let the running time be T(n). $T\left(n \right )\geqslant O\left (n^{2} \right )$ means that $T\left(n \right )\geqslant f\left(n \right )$ for some function f(n) in the set $O\left(n^2 \right )$ , This statement holds for any running time T(n), since the function g(n)=0 for all n is in $O\left(n^2 \right )$ ,and running times are always nonnegative. Thus, the statement tells us nothing about the running time.

3.1-4 Is $2^{n+1} = O\left(2^n \right )$ ? Is $2^{2n} = O\left(2^n \right )$ ?

　　 $2^{n+1} = O\left(2^n \right )$ ,but $2^{2n} \neq O\left(2^n \right )$ .

　　To show that $2^{n+1} = O\left(2^n \right )$ , we must find constants c, $n_{0}>0$ such that $0\leq 2^{n+1}\leq c*2^n \, for\,all\,n \leq n_{0}$ .

　　Since $2^{n+1}=2*2^n$ for all n, we can satisfy the definition with c=2 and $n_{0}=1.$

　　To show that $2^{2n}\neq O \left( 2^n\right)$ , assume there exist constants c, $n_{0}>0$ such that $0\leq 2^{2n}\leq c*2^n \, for\,all\,n \leq n_{0}$ .

　　Then $2^{2n}= 2^n*2^n \leqslant c*2^n \Rightarrow 2^n \leqslant c$ . But no constant is greater than all $2^n$ , and so the assumption leads to contradiction.