[Lazarus] Info on the big-O notation

Alexander Klenin klenin at gmail.com
Sat May 11 07:57:57 CEST 2019


On Fri, May 10, 2019 at 9:46 PM Graeme Geldenhuys via lazarus
<lazarus at lists.lazarus-ide.org> wrote:
>
> On 10/05/2019 12:01 pm, Graeme Geldenhuys via lazarus 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
>
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

--
Alexander S. Klenin


More information about the lazarus mailing list