Re: Normalisation

From: Jan Hidders <jan.hidders_at_REMOVETHIS.pandora.be>
Date: Wed, 13 Jul 2005 21:52:41 GMT
Message-ID: <J2gBe.144131$zb3.7653479@phobos.telenet-ops.be>

Jon Heggland wrote:
> 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.

Yeah, that's right, you're an engineer, you don't need to know theory. :-(

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

Good Lord. So let me get this straight. You are close to getting your PhD in computer science but you are not capable of giving correctly the time and space complexity in big-Oh notation of even a very simple algorithm? I hope for your sake and that of your university that you are trolling here. 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?

Of course. We are talking about the worst-case theoretical complexity here. Note btw. that when we start talking about DNA data and satellite information such sizes are suddenly not so theoretical anymore.

> Is that an issue for turing tape, anyway?

Yes, even more so. Btw. it's named after Alan Turing so you should write it with a capital.

Jan Hidders

Received on Wed Jul 13 2005 - 16:52:41 CDT