6
$\begingroup$

I know that square-root of n is space-constructible. I can't prove it by the space-constructible definition. How can I show that only $\sqrt{n}$ space is used?

  • 1
    I don't know what space-constructible means. I know $\sqrt n$ is "Euclid-constructible," that is, I can show you how to construct it with ruler and compass, if that's what you want.2012-01-28
  • 3
    @Gerry: The tag says "complexity," so...2012-01-28
  • 1
    Thanks. space-constructible means that it is possible to construct in o(n) space from 1^n to the binary representation of f(n). in our case f(n) is sqrt. Maybe the Euclid-constructible can help.2012-01-28
  • 0
    I am not sure here, but $\sqrt{x}$ is a nice function, so the Newton method should work nicely. Not sure if it converges fast enough though.... Basically, the Newton method om this case leads to the following iteration $x_0 =[ \sqrt{n}]$ (I think this is the best starting value) and uses $x_{n+1}=\frac{x_n + \frac{2}{x_n}}{2}$.2012-01-28
  • 0
    Relevant [1](http://math.stackexchange.com/questions/21231/importance-of-constructible-functions) and [2](http://cl-informatik.uibk.ac.at/teaching/ss07/alth/ohp/week5-2x2.pdf).2012-01-28
  • 4
    @anon, my comment was intended to extract some useful information from OP. I think it succeeded.2012-01-28
  • 4
    You don't need anything nearly so complicated as Newton - keep in mind that there are no time bounds on the construction. Just test all the numbers $t$ from 1 forward until you find one with $t^2\gt n$. This is easy to do in $O(\log n)$ space just by using binary.2012-01-28
  • 0
    @Eyal: Note that Wikipedia specifies using $O(f(n))$ space rather than the $o(n)$ you quote in your comment. I assume that when $f(n)$ grows slower than linearly, you're supposed to imagine a read-only input tape and a restricted-length working tape.2012-01-29
  • 0
    Henning, exactly. There is the definition of space constructibility. and I need to prove that sqrt(n) applies to it.2012-01-29
  • 0
    @Steven: going forward from 1 was one of my thoughts. I just wasn't sure. Seems that this is the way.2012-01-29
  • 0
    The input is $1^n$. That means writing a binary representation of the input requires $n$ digits, not $\log n$.2012-01-30
  • 1
    @Orgad, when dealing with space complexity we normally use separate input (read only), output (write only), and working (r/w) tapes. The space is working tape space.2012-01-31

1 Answers 1