464,662 Members | 1,281 Online Need help? Post your question and get tips & solutions from a community of 464,662 IT Pros & Developers. It's quick & easy.

# String Concatenation O(n^2) (was: Re: Explaining Implementing aBinary Search Tree.)

 P: n/a Summary: can't verify big O claim, how to properly time this? On Jun 15, 2:34 pm, "Terry Reedy" | def __str__ (self): string appending is an O(n**2) operations. The usual idiom, applied here, would be slist = ['('], slist.append(str(self.value)), .... return ''.join(slist). In other words, collect list of pieces and join at end. This is interesting. I had never attempted to verify a big O statement before, and decided that it would be worth trying. So I wrote some code to collect data, and I can't find that it goes quadratic. I have the graph at http://kasterma.wordpress.com/2008/0...concatenation/ It looks piecewise linear to me. The code I used to collect the data is as follows: ************************************************** *********************** import time NUMBER = 100 # number of strings to concatenate at given length JUMP = 500 # jump (and start length) of length of strings END = 100001 # longest length string considered def randomString (length): """ returns a random string of letters from {a,b,c,d} of length """ string = "" for i in range (0,length): string += choice ("abcd") return string def randomStrings (number, length): """ returns an array of number random strings all of length """ array = [] for i in range (0, number): array.append (randomString (length)) return array TimingData = [] for length in range (JUMP, END, JUMP): array1 = randomStrings (NUMBER, length) array2 = randomStrings (NUMBER, length) starttime = time.clock () for i in range (0, NUMBER): string = array1 [i] + array2 [i] endtime = time.clock () print "length", length, "done" TimingData.append ([length, 1000* (endtime-starttime)]) # to get a better looking graph multiply by 1000 sagefile = open ('stringConcatGraph.sage', "w") sagefile.write ("points =" + str (TimingData) + "\n") sagefile.write ("graph = line (points)\n") sagefile.write ("graph.show ()\n") sagefile.close () Jun 27 '08 #1 