Possible mistake in google's python code samples

[Michael Frysztacki]

Hi,

Im doing google's python course regarding basic stuff like working with list's and so on.

Google provides some tasks and solutions. However check out this google's snippet:

 # E. Given two lists sorted in increasing order, create and return a merged      

  1 # list of all the elements in sorted order. You may modify the passed in lists.  

  2 # Ideally, the solution should work in "linear" time, making a single            

  3 # pass of both lists.                                                                                           

  4 def linear_merge(list1, list2):                                                                                 

  5     # +++your code here+++                                                                                      

  6     # LAB(begin solution)                                                                                       

  7     result = []                                                                                                 

  8     # Look at the two lists so long as both are non-empty.                       

  9     # Take whichever element [0] is smaller.                                                                    

 10     while len(list1) and len(list2):                                                                            

 11         if list1[0] < list2[0]:                                                                                 

 12             result.append(list1.pop(0))                                                                         

 13         else:                                                                                                   

 14             result.append(list2.pop(0))                                                                         

 15                                                                                                                 

 16     # Now tack on what's left                                                                                   

 17     result.extend(list1)                                                                                        

 18     result.extend(list2)                                                                                        

 19     return result                                                                                               

 20     # LAB(replace solution)                                                                                     

 21     # return                                                                                                    

 22     # LAB(end solution) 

Above the method is written that it should work in linear time, however the solution provided by google works in N^2 because of the pop(0) operation on the list.

Is my assumption correct ?

[ahmed fahmy]

Yes !
I think so too.
pop(0) will take O(n) time , "shifting" everything one place to the left each time it's called.

[Mihai Matache]

I don't think it passes twice. The lists are already sorted so take l1[1,3,5,6,7] and l2[2,3,4,7,8,9]

l1[0] =1 and l2[0] = 2 so the next thing is 

    result.append(list1.pop(0))  which leaves l1 to be l1 == [3,5,6,7]

the next element to be teste in the if are :

l1[0] = 3 and l2[0]=2 so we take l2[0]

    result.append(list2.pop(0))  which leaves l2 to be l2 == [3,4,7,8,9]

The process goes on until one of the lists is empty, in this case l2 will be left and all the remaining elements will be aded to the result list.

In my example result will be 

result[1,2,3,3,4,5,6,7,7,8,9], but the lists will have been passed through only once