What is the mathematical definition of f(n) and O(f(n))

Question

Can someone please give the mathematical definition of f(n) and O(f(n))?

One is "function of n" and the other is "Of the order of a function n". — duffymo, Jan 02 '16 at 22:42
[Plain English explanation of Big O](http://stackoverflow.com/q/487258/3789665) — greybeard, Jan 03 '16 at 02:02

score 1 · Answer 1 · answered Jan 03 '16 at 02:18

You can check this page to see a math definition of big-O notation.

Let f and g be two functions defined on some subset of the real numbers. One writes

if and only if there is a positive constant M such that for all sufficiently large values of x, the absolute value of f(x) is at most M multiplied by the absolute value of g(x). That is, f(x) = O(g(x)) if and only if there exists a positive real number M and a real number x0 such that

In many contexts, the assumption that we are interested in the growth rate as the variable x goes to infinity is left unstated, and one writes more simply that f(x) = O(g(x)).

What is the mathematical definition of f(n) and O(f(n))

1 Answers1