InfluentialPoints.com
Biology, images, analysis, design...
Use/Abuse Principles How To Related
"It has long been an axiom of mine that the little things are infinitely the most important" (Sherlock Holmes)

Search this site

 

 

Just a note

If you are used to standard mathematical notation you may find this all rather puzzling, partly because we use round square and curly brackets interchangeably, and partly because O(1/n2) looks like the standard 'function' notation - and if that is true something is seriously wrong with our math. (That is true, but this is not our maths.)

In fact this is 'big O notation', asymptotic notation, or Bachmann-Landau notation - and is used to describe the 'limiting behaviour' of a function for very large (or very small) arguments.

    For example:
  • if F(N) is a function of N, and F(N) = 8N2 - 2N + 10
  • then the bigger N is the more its 'highest order term' will dominate the outcome.
      So if N=1000
    • then 8N2 is 4000 times larger than 2N,
    • and 8N2 is 800000 times bigger than 10
      Note: since N0equals 1, 10=10N0, so 10 has the lowest order in terms of N
  • Therefore when N is really large
    • for most practical purposes the lower order terms would have a negligible impact when evaluating F(N)
    • and if we ignore the constant for sake of generality, it is N2 which determines the 'order' of evaluating F(N)
        More formally, as N approaches infinity, we say F(N) has order O(N2), or F(N) is from a set of functions that are dominated by O(N2).
      • Writing F(N) = O(N2) is therefore misleading, albeit common.

      Conversely,

    • if F(n) = a/n2 + b/n3 + c/n4...
    • when n is large the contribution of b/n3 + c/n4... becomes vanishingly small,
    • and, for any given value of a, the order of the outcome is dictated by 1/n2

    For more about big-O (and other Bachmann-Landau notation) see en.wikipedia.org/wiki/Big_O_notation