[not Lazarus specific, but more a general programming question]
Has anybody got a good URL or document or summary email that explains
the big-O notation? It is often used to describe a task/method/algorithm
to say how quick or efficient it runs, or how well coded your method
might be. I kind-of have an idea how it works, but I would really like
to solidify my knowledge of it.
An example usage would be something like:
There are multiple ways to implement a "find the longest palindrome"
function. A simple solution would result in O(n^2) runtime, and a well
optimised solution would produce a O(n) runtime.
Sorry for intervening, but I teach this topic frequently, so I feel
compelled to make sure student is not mislead :)
The site you mentioned is nicely looking and is not technically wrong,
but still omits enough to create an illusion of understanding while
being slightly misleading.
This is ok for school pupils, but probably not for college / higher education.
Main missing points:
1) Big-O notation is a generic concept from basic calculus. While it
is commonly used for worst-case time analysis,
it can as well be used for best, average, amortized times as well as for
functions which have no relation to algorithmic complexity.
2) The whole point of using big-O in complexity analysis is to
abstract away "small" implementation
details like programming language, physical hardware, compiler
quality etc. So that algorithms
may be divided into sets of "similar" complexity. This is what
O(f(n)) essentially is -- a set of functions
which grow "no faster than" f(n) (in precisely defined sense).
3) Note the phrase "no faster than" as opposed to "as fast as" in
Big-O is actually an *upper bound* on growth. So a linear function
f(n) = n is not only in O(n), but also
in O(n^2), O(n^3) etc. There are similar notations for "no slower
than" (small-o), "as fast as" (omega) etc.
3) While "beware of writing quadratic algorithm accidentally" is
indeed a good rule of thumb
for young, naive or just lazy programmers, the real trouble begins
higher on the complexity ladder,
around O(2^n). There is a long and fascinating story about P, NP and
the most important unresolved question in math.
You can read about it all around the Internet -- just do not limit
yourself to oversimplified cartoon-style versions,
you will miss most interesting stuff :)
4) I would recommend Wikipedia as a starting point of reading, including