Algorithm design and analysis class

Problem $2(9$ points$)$

Insertion sort can be expressed as a recursive procedure. To sort $A[1$dotsn$],$ we recursively sort $A[1$dotsn$-1]$ and then insert $A[n]$ into the sorted array $A[1$dotsn$-1].$ Write a recurrence for the running time of this recursive version of insertion sort.

Problem $3(30$ points$)$ For parts $($a$)-($e$),$ decide if it is true or false. If the statement is true, then prove it $($to prove it you will either need to use the definition and find constants or use the limit laws$).$ If the statement is false, then give a reason or a counterexample. Then answer part $($f$).$

$8n^3=O(n^4).$

$n^{3}in(n^4)$

$2^n$inO$(2^{n+1})$

$n!in((n+1)!)$

What does $O(1)$ mean?

What does $(1)$ mean?

Problem $4(21$ points$)$

Let $f(n)$ and $g(n)$ be asymptotically positive functions. Prove or disprove each of the following conjectures.

a$.f(n)=O(g(n))$ implies $g(n)=O(f(n))$

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

c$.g(n)=(f(n))$ implies $f(n)=O(g(n)).$