$3$ Big$-$ Analysis: Algorithms on Numbers

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 $$ and $$ produces the sum $+$ 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 $$ and $$

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

the carry. Once all bits of $$ and $$ 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 $$th bit for

any $).$

$($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

$3$

row with one sentence, using facts that you already know about the growth of

functions.$)$

$()(+)($log $$ log $)($log $+$ log $)$

$()(+)($log $$ log $)($log $+$ log $)$