Why is the addition function exponential for k-bit integers providing only zero, equality and the successor functions?

Question

I'm currently reading the elements of programming book and have come across a section I don't quite understand

A computational basis for a type is a finite set of procedures that enable the construction of any other procedure on the type. A basis is efficient if and only if any procedure implemented using it is as efficient as an equivalent procedure written in terms of an alternative basis. For example, a basis for unsigned k-bit integers providing only zero, equality, and the successor function is not efficient, since the complexity of addition in terms of successor is exponential in k

Given the successor function , wouldn't addition be linear? e.g. getting get the result of a + b the complexity would be O(b) starting from a? I know this is likely not the case as I'm sure the book knows more about what it's saying than me, but can someone explain why this operation would be exponential?

Answer 1

The complexity of getting "the result of a + b" would indeed "be O(b) starting from a".

However, b is a log(b)-bit integer, and O(b) = O(2^(log(b))).

Answer 2

From the Wikipedia article on time complexity:

In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input.

(Wikipedia references Sipser, Introduction to the Theory of Computation, for the above sentence.)

In your case, the "length of the string representing the input" is the number of bits representing $a$ and $b$, call it $k$. Since $O(b) = O(2^k)$, this is exponential time.

To put this into perspective, imagine you are a computer. Someone loads an algorithm into your CPU and you're just blindly working on the input bits that you are given. To you, it really doesn't matter what these bits represent; they could be numbers, sets, English words, doesn't matter. You're just following the step-by-step procedure. Thus when talking about running time, it only makes sense to consider the number of bits, not the potential numbers they represent.

It might now get confusing when you think of things like sorting. Why don't we consider the number of bits of the array elements when discussing the running time of a sorting algorithm? Well, we do, it's just that there is the implicit assumption that all the array elements can be represented by a constant number of bits (e.g., 32-bit integers). Thus the asymptotic running time is unaffected.

Answer 3

The average magnitude $m$ of a number of $k$ binary digits is an exponential function of $k$ (because $k= \lfloor{\log_2{m}}\rfloor + 1$, $ m>0$). Using only zero, equality, and the successor function, the best you can get is an algorithm that is in $\Theta(2^k)$.

Fortunately, using other procedures you have algorithms that are much better than that.