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

© Vsevolod Domkin 2021

V. DomkinProgramming Algorithms in Lisphttps://doi.org/10.1007/978-1-4842-6428-7_2

2. Algorithmic Complexity

Vsevolod Domkin¹  

(1)

Kyiv, Ukraine

 

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. 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. By and large, 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 ...