Let $$ and $$ be two nonnegative integers, represented in binary. Assume for concreteness

that there are no leading zero$$s in the binary representations; for example the number three

is represented as $11$ and not as $00011.($If you prefer, you can assume that the numbers are

represented in decimal and answer the problem for decimal addition and division operations,

it won$$t change the answer.$)$

$1.$ Addition. A standard algorithm for adding x and y produces the sum x $+$ y by working

from low$-$order bits to high$-$order bits of each number. A carry bit is initially set to $0.$

The algorithm iteratively produces an output bit from the carry and two bits of x and y

$($or just one of these if all bits of the other have already been considered$),$ and updates

the carry. Once all bits of xand y are considered, if the carry is $1,$ then a final high$-$order

$1$ is output.

$($a$)(2$ marks$)$ Give a tight big$-$ bound on the running time of this algorithm as a

function of $$ and $.$ Justify your answer. You may assume that you can access the

bits of the numbers in constant time $($i$.$e$.,$ you can get the value of the ith bit for

any i$).$

$($b$)(2$ marks$)$ Which categories does the running time of the standard addition algorithm

belong to$?$ Choose as many as apply. $($Your justification for your choices need

not consider all options separately; may be able to justify your choices across a