Note: Please write your solutions on the answer sheet.

Let $f(n)$ and $g(n)$ be functions from positive integers to positive reals. We say $f=O(g)($which means that $"f$ grows no faster than $g")$ if there is a constant $c>0$ such that $f(n)cg(n).$ If $g(n)$ grows no faster than $f(n),$ we say $f=(g).$ If $f=O(g)$ and $f=(g),$ we say $f=(g).(1)$ Prove the relation of $f(n)$ and $g(n)$ for the following questions. $(6\text{'})(2)$ Give Big$-$O notations of each formular. $(4\text{'})$

$(1)f(n)=n+100,g(n)=3n+20$

$(2)f(n)=n^3+100,g(n)=9n^2+10$

In $64-$bit computers, the maximum value that a signed integer variable can represent is $2^{63}-1,$ while an unsigned integer variable can represent a maximum value of $2^{64}-1.$ In other words, integer variables can only represent numbers with the length smaller than $64$ bits in binary system. If we want to get the addition result of two integers with $100$ bits of binary system like $"1010..\mathrm{.}1110"$ and $"1001..\mathrm{.}1011"($which are too large and can only be stored in string variables$),$ the original addition operation of computers can not be used. Please design an algorithm to implement the addition of two string variables with more than $100$ bits for each. $(12\text{'})$