1

I'm trying to read Sipser's book chapter 10 on page 399

and there's a paragraph that says

One way to determine whether a number is prime is to try all possible 
integers less than that number and see whether any are divisors, also 
called factors. That algorithm has exponential time complexity because 
the magnitude of a number is exponential in its length

What does "the magnitude of a number is exponential in its length" exactly mean? I don't understand the difference between magnitude and length of a number

testinggnitset ser
  • 161
  • I think you may want to remove the complex-analysis tag from this post, as it has nothing to do with complex-analysis – awright96 Apr 23 '17 at 21:03

2 Answers2

1

Express a number $k$ in binary form. The number of bits required to express $k$ in this way is $\lceil \log_{2}(k) \rceil$.

In the opposite direction, using $n$ bits, you can express numbers from $0$ to $2^{n}-1$. Thus the maximum magnitude of an $n$ bit number is $O(2^{n})$.

Brian Borchers
  • 10,563
0

I believe he means that as the length of the number (the number of digits the number is represented by) increases linearly, the magnitude, or distance from 0, of the the number increases exponentially. Example:

100 only has 50 % more digits than 10, but 100 is 1000% larger than 10.

awright96
  • 425