Re: Normalisation

In article <smWAe.143397$1f4.7471162_at_phobos.telenet-ops.be>, jan.hidders_at_REMOVETHIS.pandora.be says...
> > 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?
> :-)

I guess not. :) I can estimate the memory use of my algorithms, but I haven't felt the need for turing tape before now.

> 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.

Seriously?

> > 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.

I'm not versed in storing counters on turing tapes, but in my favourite programming languages, that counter takes constant space. Unless the string is *really* long (like over four billion characters)---is that what you are talking about? I'll admit there is a logarithm there, but do you really consider that significant? Is that an issue for turing tape, anyway?

> How much work, on average, will it take to increment that counter?

You'll have to do it as many times as the length of the string. You'll have to hint more if I am to find the hidden logarithm here. :)

-- 
Jon