On Fri, May 10, 2019 at 9:46 PM Graeme Geldenhuys via lazarus

<

[hidden email]> wrote:

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

--

_______________________________________________

lazarus mailing list

[hidden email]
https://lists.lazarus-ide.org/listinfo/lazarus