Problem $1-1.$ Asymptotic Notation

For each of the following statements, decide whether it is always true, never true, or sometimes true for asymptotically nonnegative functions $f$ and $g.$ It it is always true or never true, explain why. It is sometimes true, give one example for which it is true, and one for which it is false.

a$)f(n)=O(f(n{)}^2)$

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

c$)f(n)+O(f(n))=(f(n))$

d$)f(n)=(g(n))$ and

e$)f(n)O(g(n))$ and $g(n)O(f(n))$

Problem $1-2.$ Recurrences

Give asymptotic upper and lower bounds for T$($n$)$ in each of the following recurrences. Assume that $T(n)$ is constant for $n10.$ Make your bounds as tight as possible, and justify your answers.

a$)T(n)=2T(\frac{n}{3})+nlgn$

b$)T(n)=3T(\frac{n}{5})+l{g}^{2}n$

c$)T(n)=T(\frac{n}{2})+2^n$

d$)T(n)=T(\sqrt[\phantom{2}]{n})+(lglgn)$