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?
bignums) 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