[Lazarus] Info on the big-O notation

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

[Lazarus] Info on the big-O notation

Free Pascal - Lazarus mailing list
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
--
_______________________________________________
lazarus mailing list
[hidden email]
https://lists.lazarus-ide.org/listinfo/lazarus
Reply | Threaded
Open this post in threaded view
|

Re: [Lazarus] Info on the big-O notation

Free Pascal - Lazarus mailing list
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


Regards,
  Graeme
--
_______________________________________________
lazarus mailing list
[hidden email]
https://lists.lazarus-ide.org/listinfo/lazarus
Reply | Threaded
Open this post in threaded view
|

Re: [Lazarus] Info on the big-O notation

Free Pascal - Lazarus mailing list
On Fri, May 10, 2019 at 9:46 PM Graeme Geldenhuys via lazarus
<[hidden email]> 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
--
_______________________________________________
lazarus mailing list
[hidden email]
https://lists.lazarus-ide.org/listinfo/lazarus