Doubt on O notation.

[gfgs pedo]

hi,

I have problem understanding time complexity for the
following problem

I need to check if two strings are equal

let string one
s1=aaabbb

and string two

s2=aaabbb

We place it on a single tape turing machine

aaabbb aaabbb

the book says it takes  roughly 2n steps to match
corresponding alphabet of s1 with s2,that much i
understand.

therefore the whole computation takes O(n^2) time.
how is that,should n't be O(2n)

the same if placed on a two tape turing machine is as
shown
tape 1: aaabbb
tape2 : aaabbb

and they are compared simultaneouly and have a time
complexity of O(n) which is understandable.

How ever  i didnt get how we get O(n^2) in the
previous case.

In automata  the number of sentential
forms cannot exceed 
M=|p|+ |p^2| + ...+ |p|^(2|w|) where w is the length
of the input string.p is the finite set of
productions.
I dont see how it is applicable here.
pls help.Thank you.

Regards Data.

__________________________________________________
Do You Yahoo!?
HotJobs - Search Thousands of New Jobs
http://www.hotjobs.com