patternModerate
Why is the addition function exponential for k-bit integers providing only zero, equality and the successor functions?
Viewed 0 times
whythebitequalityexponentialsuccessoradditionfunctionprovidingfor
Problem
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 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?Solution
The complexity of getting "the result of
However,
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))).Context
StackExchange Computer Science Q#44146, answer score: 10
Revisions (0)
No revisions yet.