Which operations in Common Lisp programs are to be considered sufficiently primitive so as to count for a single "step" in algorithmic analysis? How widely do modern lisps vary in their implementation?
Certainly arithmetic with small integers would count as a single step, but what about larger numbers? And what about considering the difference between reverse
and nreverse
? Specifically, is nreverse
theta of reverse
? What about all of the array and sequence operations? Also, how do macros figure in - how should I think about macros when analyzing complexity?