Name: Programming Algorithms in Lisp: Writing Efficient Programs with Examples in ANSI Common Lisp
Author: Vsevolod Domkin

Cover of Programming Algorithms in Lisp: Writing Efficient Programs with Examples in ANSI Common Lisp

Kindle

Vsevolod Domkin

68 highlights · 10 notes · last read March 2025

Highlights I wrote a note on are shown in full. The other 58 are scrambled: the words are the author's, so here you only see where in the book I underlined something.

Complexity is a point that will be mentioned literally on every page of this book; the discussion of any algorithm or data structure can’t avoid this topic. After correctness, it is the second most important quality of every algorithm.
Page 7

My note Complexity & Correctness

Moreover, often correctness alone doesn’t matter if complexity is neglected, while the opposite is possible: to compromise correctness somewhat in order to get significantly better complexity.
Page 7

My note Its possible to compromise correctness?

algorithm theory differs from other subjects of CS in that it concerns not about presenting a working (correct) way to solve some problem but about finding an efficient way to do it, where efficiency is understood as the minimal (or admissible) number of operations performed and occupied memory space.
Page 7

My note Algorithms > Correctness AND complexity

in most of the cases, measuring complexity is a matter of simple counting.
Page 7

My note Comexity is a matter of counting!!

If we sum this all up, we’ll get n * m * 4 as an upper limit, for the worst case when each sequent array element is larger than the previous. As a rule of thumb, each loop adds multiplication to the formula, and each sequential block adds a plus sign.
Page 8

My note Each loop: multiplcation sign *
Each sequence : plus sign +

There exists a special notation—Big-O—used to simplify the representation of end results of such complexity arithmetic. In it, all constants are reduced to 1, and thus m * 1 becomes just m, and also since we don’t care about individual array dimension differences, we can just put n * n instead of n * m. With such simplification, we can write down the final complexity result for this function: O(nˆ2). In other words, our algorithm has quadratic complexity (which happens to be a variant of a broader class called “polynomial complexity”) in array dimensions. It means that by increasing the dimensions of our matrix ten times, we’ll increase the number of operations of the algorithm 100 times.
Page 8

My note QUADRATIC Polynomial complexity

There are six major complexity classes of algorithms: Constant-time (O(1)) Sublinear (usually, logarithmic—O(log n)) Linear (O(n)) and superlinear (O(n * log n)) Higher-order polynomial (O(nˆc), where c is some constant greater than 1) Exponential (O(cˆn), where c is usually 2 but, at least, greater than 1) Just plain lunatic complex (O(n!) and so forth)—I call them O(mg), jokingly Each
Page 8

My note SIX COMPLEXITY CLASSES OF BIG O

Finally, besides execution time complexity, there’s also space complexity, which instead of the number of operations measures the amount of storage space used proportional to the size of the input.
Page 10

My note EXECUTION TIME COMPLEXITY
SPACE COMPLEXITY

Lisp programs consist of forms that are evaluated by the compiler.
Page 12

My note LISP EQUALS FORMS THAT ARE EVALUATED BY THE COMPILER

three ways to evaluate a Lisp compound expression:
Page 12

My note Three ways to EVALUATE a compound expression

Amazon ↗ · Goodreads ↗