Big O Notation - Example

Example

In typical usage, the formal definition of O notation is not used directly; rather, the O notation for a function f(x) is derived by the following simplification rules:

  • If f(x) is a sum of several terms, the one with the largest growth rate is kept, and all others omitted.
  • If f(x) is a product of several factors, any constants (terms in the product that do not depend on x) are omitted.

For example, let, and suppose we wish to simplify this function, using O notation, to describe its growth rate as x approaches infinity. This function is the sum of three terms: 6x4, −2x3, and 5. Of these three terms, the one with the highest growth rate is the one with the largest exponent as a function of x, namely 6x4. Now one may apply the second rule: 6x4 is a product of 6 and x4 in which the first factor does not depend on x. Omitting this factor results in the simplified form x4. Thus, we say that f(x) is a big-oh of (x4) or mathematically we can write f(x) = O(x4). One may confirm this calculation using the formal definition: let f(x) = 6x4 − 2x3 + 5 and g(x) = x4. Applying the formal definition from above, the statement that f(x) = O(x4) is equivalent to its expansion,

for some suitable choice of x0 and M and for all x > x0. To prove this, let x0 = 1 and M = 13. Then, for all x > x0:

begin{align}|6x^4 - 2x^3 + 5| &le 6x^4 + |2x^3| + 5\ &le 6x^4 + 2x^4 + 5x^4\ &le 13x^4\ &le 13|x^4|end{align}

so

Read more about this topic:  Big O Notation

Other articles related to "example":

Finite Model Theory - Basic Challenges - Characterisation of A Class of Structures - Example
4 ... Next we have to scale the structures up by increasing m ...
Wave Front Set - Definition - Example
... Then the projection on the first component of a distribution's wave front set is nothing else than its classical singular support, i.e ... the complement of the set on which its restriction would be a smooth function ...
Example

Example may also refer to:

  • Example (musician), a British musician
  • Example, Florida rock band For Squirrels' sole major-label album, released in 1995
  • example.com, example.net, example.org, example.edu and .example, domain names reserved for use in documentation as examples
  • HMS Example (P165), an Archer-class patrol and training vessel of the British Royal Navy
  • The Example, a 1634 play by James Shirley
  • The Example (comics), a 2009 graphic novel by Tom Taylor and Colin Wilson

Famous quotes containing the word example:

    Our intellect is not the most subtle, the most powerful, the most appropriate, instrument for revealing the truth. It is life that, little by little, example by example, permits us to see that what is most important to our heart, or to our mind, is learned not by reasoning but through other agencies. Then it is that the intellect, observing their superiority, abdicates its control to them upon reasoned grounds and agrees to become their collaborator and lackey.
    Marcel Proust (1871–1922)