commit 3ffc75060a15d60e2fa9f458e30b8685af2642c5 Spenser Truex <spensertruexonline@gmail.com> 2019-09-14 13:54:16 -0700 latex complexity
README.md | 9 --------- README.org | 23 +++++++++++++++++++++++ 2 files changed, 23 insertions(+), 9 deletions(-)
diff --git a/README.md b/README.md deleted file mode 100644 index 17ab644..0000000 --- a/README.md +++ /dev/null @@ -1,9 +0,0 @@ -# Usage -The only external function is `len`. - -```common-lisp -(len <integer or list> <list> &optional (<predicate> #'=)) -(len 3 '(1 2 3)) ;=> T -(len '(a b c) '(1 2 3)) ;=> T -(len 3 '(1 2 3) #'/=) ;=> NIL -``` diff --git a/README.org b/README.org new file mode 100644 index 0000000..13d36b1 --- /dev/null +++ b/README.org @@ -0,0 +1,23 @@ +#+TITLE: Length Comparison +#+AUTHOR: Spenser Truex +#+EMAIL: web@spensertruex.com +* Purpose +Provide /short-circuit/ length comparisons. +* Usage +The only external function is `len`. +#+BEGIN_SRC common-lisp +(len <integer or list> <list> &optional (<predicate> #'=)) +(len 3 '(1 2 3)) ;=> T +(len '(a b c) '(1 2 3)) ;=> T +(len 3 '(1 2 3) #'/=) ;=> NIL +#+END_SRC +* Complexity + Comparing the length of some lists with lengths n_i in *N* requires going + across all of their elements. +\begin{equation} +O(\sum{}_{n=0}^{n-1}n_i) +\end{equation} + +With a short-circuit length comparsion, the worst case scenario is the same, +with the best case \begin{equation}O(1)\end{equation} and average case +\begin{equation}O(\min{N})\end{equation}.