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