0
$\begingroup$

Following is the excerpt from wiki

If numerical data are represented in terms of digits (or bits), then the naive algorithm also entails storing approximately $2n$ times the number of bits of $x$ (the evaluated polynomial has approximate magnitude $x^n$, and one must also store $x^n$ itself). By contrast, Horner's method requires only $n$ additions and $n$ multiplications, and its storage requirements are only $n$ times the number of bits of $x$.

I don't understand, how?

$\endgroup$
  • $\begingroup$ Okay. So I read this : en.wikipedia.org/wiki/… . I don't think the explanation was that obvious. Any comments? $\endgroup$ – PleaseHelp May 9 '16 at 17:15
  • 1
    $\begingroup$ What exactly don't you understand? We can give you a better answer if you tell us what part of the excerpt you do understand and what was the first part that didn't make sense or that you didn't understand. What have you tried? Have you tried working out the space complexity of Horner's method yourself? What did you come up with? $\endgroup$ – D.W. May 9 '16 at 17:58
  • $\begingroup$ @D.W. I was looking for a storage variable that needed $2n|x|$ space. Instead it turned out that we need two variables with $n|x|$ space. $\endgroup$ – PleaseHelp May 10 '16 at 4:05
2
$\begingroup$

Storing the output requires roughly $n|x|$ bits (where $|x|$ is the size of $x$ in bits); this is since the numbers involved have magnitude $\Theta(x^n)$. This is all that Horner's method requires, since it only keeps track of one value, the current "partial sum".

In contrast, the naive method keeps track of two values: the current partial sum, and also the current power of $x$. Each of these requires (towards the end of the process) roughly $n|x|$ bits to store, and both of them require $2n|x|$ bits in total.

$\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.