Complexity of splits

[Aahz]

In article <jeapy-98A462.15570212052003 at malibu.unice.fr>,
Jean-Guillaume Pyraksos  <jeapy at free.fr> wrote:
>
>As I am digging into my Python studies, I started translating some 
>elementary Lisp recursive algorithms...
>
>def length(L):
>   if not(L): 
>      return 0
>   return 1 + length(L[1:len(L)])
>
>is (?) the Pythonization of the Lisp function:
>
>(defun length (L)
>  (if (not L)
>      0
>      (+ 1 (length (cdr L)))))
>
>If n is the length of L, then the Lisp algorithm is O(n) but the Python 
>algorithm is O(n^2) as L([1:len(L)]) builds a n-1 elements list. Am i 
>wrong ? I chose a split as it seems that taking the cdr of a list is not 
>a primitive operation in Python, did I miss it ? Probably. What's the 
>name of that operation  so that the recursive algorithm stays O(n) ? I 
>don't want (for now) to translate it into a loop.

For the fun of showing off my ignorance, here's what I think is the
answer to your question:

Python lists are vectors; Lisp lists are linked lists.  They are
fundamentally different data types with different O() behavior for
different algorithms -- you can't index into a Lisp list in O(1) time,
for example.  (I believe Lisp has "array" for that.)  If you want to
implement the precise equivalent of the Lisp algorithm in Python, you
need to create a Python class that implements a linked list.
-- 
Aahz (aahz at pythoncraft.com)           <*>         http://www.pythoncraft.com/

"In many ways, it's a dull language, borrowing solid old concepts from
many other languages & styles:  boring syntax, unsurprising semantics,
few automatic coercions, etc etc.  But that's one of the things I like
about it."  --Tim Peters on Python, 16 Sep 93