$(2$ points$)$ Modified Exercise $2\mathrm{.}1\mathrm{.}8$ For each of the following functions, indicate how much the function's value will change if its argument is increased fourfold.

a$.lo{g}_{2}n$

d$.n^2$

e$.n^3$

f$.2^n$

$(2$ points$)$ Modified Exercise $2\mathrm{.}1\mathrm{.}9$ Indicate whether the first function of each of the following pairs has a smaller, same, or larger order of growth $($to within a constant multiple$)$ than the second function.

a$.n(n+1)$ and $2000n^2$

b$.100n^2$ and $0\mathrm{.}01n^3$

d$.(lo{g}_{2}n{)}^2$ and $lo{g}_2{n}^2$

f$.(n-1)!$ and $n!$

$(2$ points$)$ Modified Exercise $2\mathrm{.}2\mathrm{.}2$ Use the informal definitions of $O,,$ to determine whether the following assertions are true or false

a$.\frac{n(n+1)}{2}$inO$(n^3)$

b$.\frac{n(n+1)}{2}$inO$(n^2)$

c$.\frac{n(n+1)}{2}in(n^3)$

d$.\frac{n(n+1)}{2}in(n)$

$(2$ points$)$ Exercise $2\mathrm{.}2\mathrm{.}3($a$-$d$).$ For each of the following functions, indicate the class $(g(n))$ the function belongs to$.($Use the simplest $g(n)$ possible in your answer. Prove your assertion. $($informal proofs are ok$)$

a$.(n^2+1{)}^{10}$

b$.\sqrt[\phantom{2}]{10n^2+7n+3}$

c$.2nlog(n+2{)}^2+(n+2{)}^{2}log(\frac{n}{2})$

d$.2^{n+1}+3^{n-1}$

$(2$ points$)$ Exercise $2\mathrm{.}2\mathrm{.}6$

a$.$ Prove that every polynomial of degree k$,p(n)=a_k{n}^k+a_{k-1}{n}^{k-1}+$cdots$+a_0,$ belongs to $(n^k)$

b$.$ Prove that exponential functions $a^n$ have different orders of growth for different values of $a>0.$

$(6$ points$)$ Modified $1\mathrm{.}4\mathrm{.}10$ Anagram checking

a$.$ Design an algorithm for checking whether two given words are anagrams, i$.$e$.,$ whether one word can be obtained by permuting the letters of the other. $($For example, the words tea and eat are

anagrams.$)$ Write the pseudocode for the algorithm.

b$.$ What is the time efficiency of the algorithm $($worst case and average case if different$)?$ Justify your answer. Clearly indicate the input size parameter and the algorithms basic operation.

c$.$ Implement your algorithm in C$++$ using the function prototype below. $($Submit separately as a text file$).$

bool isAnagram$($string$,$ string$)$;