# Re: Normalisation

Date: Tue, 12 Jul 2005 21:11:52 GMT

Message-ID: <smWAe.143397$1f4.7471162_at_phobos.telenet-ops.be>

Jon Heggland wrote:

> In article <OI5Ae.141460$zX6.7309433_at_phobos.telenet-ops.be>,

*> jan.hidders_at_REMOVETHIS.pandora.be says...
**>
*

>>Come on, Jon. How much tape does the Turing machine need that computes >>this transformation if n is the size of the input?

*>*

> Apparently, there are holes in my education---I'm more an engineer than

*> a scientist. The complexity I'm used to computing on algorithms deals*

*> with time or number of operations; both the set and string algorithms*

*> seem linear to me.*

And engineers don't have to know about space complexity of algorithms? :-) But time complexity is also different. The unary relation can be transformed in linear time, but the string transformation requires O(n.log(n)) steps.

> But if you won't bother to explain, no big deal.

I'll give you hint. For unnesting the string you need a counter. How much space will that counter take on the Turing tape. How much work, on average, will it take to increment that counter?

*> I
*

> still say both operations are trivial to perform. And why draw the line

*> at that particular place?
*

The linear-time constant-space transformation are traditionally seen as the class of computations that just do some reformatting but don't really compute anything new. Of course, this is to some extent a matter of taste and may under certain circumstances not be an appropriate definition, but if you look at what computations are in that class then it usually makes sense.

- Jan Hidders