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?
how can i prove that square root of n is space constructible
6
$\begingroup$
computer-science
computational-complexity
-
1I 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
-
1Thanks. 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
-
0I 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
-
0Relevant [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
-
4You 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
-
0Henning, 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
-
0The 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