B$.$Tech$/$Design and Analysis of Algorithms $2023-24($CSC $403)$: Assignments

Exercise Set #$1$

From CLRS $($Cormen Book$)-3^{rd}$ Edition.

Page: $52$

$3\mathrm{.}1-1$: Let $f(n)$ and $g(n)$ be asymptotically non$-$negative functions. Using the basic definition of $-$notation, prove that

max$(f(n),g(n))=(f(n),g(n)).$

$3\mathrm{.}1-2$: Show that for any real constants a and $b,$ where $b>0,$

$(n+a{)}^b=(n^b).$

$3\mathrm{.}1-4$: $,$ Is $2^{n+1}=O(2^n)?$

Is $2^{2n}=O(2^n)?$

$3\mathrm{.}1-7$: Prove that $o(g(n))(g(n))$ is the empty set.

Note: If we do not cover little$-$oh & little$-$omega, we can omit this exercise.

Page $1$ of $3$

B$.$ Tech$/$Design and Analysis of Algorithms $2023-24($CSC $403)$: Assignments

$3\mathrm{.}2-7$: Prove by induction that the $i^{th}$ Fibonacci number satisfies the equality

Where $\frac{O}{?}$ is the golden ratio and is its conjugate.

$\frac{O}{?}=\frac{1+\sqrt[\phantom{2}]{5}}{2}$

$\frac{O}{?}=\frac{1-\sqrt[\phantom{2}]{5}}{2}$

$3\mathrm{.}2-8$: Show that $klnk=(n)$ implies $k=(\frac{n}{lnn}).$