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?
bignum
s) should be O(log n) where n is the larger of the integers. There are many different algorithms for multiplication; I'm not an expert in the field, and this is likely to be implementation specific.reverse
and nreverse
can both be implemented O(n) (reverse
by a cdr-input-and-cons-output strategy; nreverse
by exchanging pointers while cdring). If I understand the unfamiliar term “theta of” correctly, then yes. Note, however, that the CL standard does not make any guarantees about time complexity.eval
/compile
, in which case you have to think about the complexity of the implementation's compiler as well) since it runs at compile time, once; only the expanded code matters.If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With