Tell me more ×
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.
up vote 4 down vote favorite

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

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.