Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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. –  Gerry Myerson Jan 28 '12 at 22:02
@Gerry: The tag says "complexity," so... –  anon Jan 28 '12 at 22:10
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. –  Eyal Golan Jan 28 '12 at 22:17
@anon, my comment was intended to extract some useful information from OP. I think it succeeded. –  Gerry Myerson Jan 28 '12 at 23:11
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. –  Steven Stadnicki Jan 28 '12 at 23:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.