Oracle FAQ | Your Portal to the Oracle Knowledge Grid |
Home -> Community -> Usenet -> comp.databases.theory -> Re: Normalisation
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? >>:-)
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.
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.
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.