analysis.theory.txt

            
   ANALYSIS  
            



LIMIT ==>                         #Value of a function as its input approaches some other value.
                                  #Notation: lim(x->c, f(x))
                                  #  - i.e. f(x) value, as x approaches c

ASYMPTOTIC ANALYSIS ==>           #Also named "asymptotics"
                                  #Function F when its input are arbitrarily large.
                                  #Notation: f(x) ~ g(x)
                                  #  - named "is order of"
                                  #  - means lim(x->∞, f(x)/g(x)) = 1
                                  #  - i.e. f and g asymptotically equivalent

FUNCTION ORDER ==>                #Asymptotic upper|lower bounding function
                                  #Notation:
                                  #  - f(x) ∈ O(g(x)):
                                  #     - named "big O"
                                  #     - g is upper bound of f
                                  #     - sometimes written f(x) = O(g(x))
                                  #        - ambiguous because not symetric
                                  #     - O(g(...)) can be shortened to O(...)
                                  #  - Ω(...):
                                  #     - named "big Omega" (Knuth definition)
                                  #     - same but lower bound
                                  #  - θ(...)
                                  #     - named "big Theta"
                                  #     - both upper|lower bound
                                  #Operations:
                                  #  - O(k*n) = O(n)
                                  #     - with k being non-0 constant, and n a variable
                                  #     - i.e. constants are usually not kept
                                  #  - O(n) + O(m) = O(max(n, m))
                                  #  - O(n) * O(m) = O(n*m)

FUNCTION DOMINATION ==>           #Function order but excluding tight bound.
                                  #Notation:
                                  #  - o(...):
                                  #     - named "small o"
                                  #  - ω(...):
                                  #     - named "small Omega"
                                  #     - same but greatest lower bound
                                  #  - Ω(...):
                                  #     - named "big Omega" (Harly-Littlewood)
                                  #     - negation of o(...), i.e. f dominated by g
                                  #     - avoid because ambiguity with big Omega, Knuth definition

ASYMPTOTIC NOTATION ==>           #Also named "Bachmann–Landau notation"
                                  #All following notations: O(...) Ω(...) θ(...) o(...) ω(...) Ω(...) ~

COMMON ORDERS ==>                 #O(1)
                                  #  - named "constant"
                                  #  - example: lookup table
                                  #O(log(log(n)))
                                  #  - named "log-logarithmic" or "double logarithmic"
                                  #O(log(n))
                                  #  - named "logarithmic"
                                  #  - example: binary search
                                  #O((log(n))^k)
                                  #  - named "polylogarithmic"
                                  #O(n^k) (0<k<1)
                                  #  - named "fractional power"
                                  #O(n^0.5)
                                  #  - named "square root"
                                  #O(n)
                                  #  - named "linear"
                                  #  - example: max(ARR)
                                  #O(n*log(n))
                                  #  - named "linearithmic", "loglinear" or "quasilinear"
                                  #  - equivalent to O(log n!)
                                  #  - example: heap sort
                                  #O(n^2)
                                  #  - named "quadratic"
                                  #  - example: bubble sort
                                  #O(n^3)
                                  #  - named "cubic"
                                  #O(n^m)
                                  #  - named "polynomial" or "algebraic"
                                  #O(m^n)
                                  #  - named "exponential"
                                  #O(m^(m^n))
                                  #  - named "double-exponential"
                                  #O(n!)
                                  #  - named "factorial"