Question

Give a big-O estimate of the complexity of the Base algorithm

procedure Base (n: positive integer, b: positive integer greater than 1)

q:=n

k:=0

while q {eq}ne

{/eq} 0

begin

{eq}a_k

{/eq}:=q mod b

q:= q div b

k:= k + 1

end

return ({eq}a_{k-1}….a_1a_0

{/eq})

EXPERT ANSWER

The complexity is going to be how many times the loop iterates. The WHILE loop executes while variable *q* NOT EQUAL to 0, and is decremented each time by the value of variable *b*, (*q=q div *

*
*