5
$\begingroup$

Suppose I have two 5-digit numbers (A and B) and two 50-digit numbers(C and D). Do the operations A+B and C+D have equal complexity in terms of time and space? or C+D is more complex due to the size of digits?

$\endgroup$
3
$\begingroup$

The complexity of arithmetic operations is typically measured in bit operations, though not everybody agrees this is the correct measure. There is a Wikipedia page listing the complexity of the best algorithms currently known for various operations, including addition and multiplication.

$\endgroup$
0
$\begingroup$

It depends on the model you use. Yuval Filmus's answer assumes you use a multitape Turing machine. This is also mentioned in the Wikipedia page:

Here, complexity refers to the time complexity of performing computations on a multitape Turing machine.

However, for example, if you use a random access machine, the time and space complexity of an arithmetic operation of any-digit numbers is considered to be $O(1)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.