Hi,

[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.

Regards,
Graeme

Graeme Geldenhuys wrote

Has anybody got a good URL or document or summary email that explains the big-O notation?

Seems all I needed was just one extra search on the Internet. :-) I found the following URL which gives an excellent explanation.

http://cooervo.github.io/Algorithms-DataStructures-BigONotation/big-O-notation.html

Regards,
Graeme

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 previous paragraph.
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 https://en.wikipedia.org/wiki/Analysis_of_algorithms