[Tutor] Question about O(N**2)

[David Rock]

The the "Logical Error" question, this was brought up:
	The big problem is this:                                                                                                      
																      
	    fullPath += [line.decode('utf-8', 'ignore').strip()]                                                                      
																      
	which is an O(N**2) algorithm. Do you know that terminology? Very                                                             
	briefly: O(1) means approximately constant time: tripling the size of                                                         
	the input makes no difference to the processing time. O(N) means linear                                                       
	time: tripling the input triples the processing time. O(N**2) means                                                           
	quadratic time: tripling the input increases the processing time not by                                                       
	a factor of three, but a factor of three squared, or nine.                                                                    
																      
	With small files, and fast computers, you won't notice. But with huge                                                         
	files and a slow computer, that could be painful.                                                                             
																      
	Instead, a better approach is:                                                                                                
																      
	    fullPath.append(line.decode('utf-8', 'ignore').strip())                                                                   
																      
	which avoids the O(N**2) performance trap.   

I have two questions:
1. How do you know that fullPath += [line.decode('utf-8', 'ignore').strip()] is an O(N**2)?
2. How do you know that fullPath.append(line.decode('utf-8', 'ignore').strip()) is not?

-- 
David Rock
david at graniteweb.com