Big O Notation - Related Asymptotic Notations - Use in Computer Science

Use in Computer Science

For more details on this topic, see Analysis of algorithms.

Informally, especially in computer science, the Big O notation often is permitted to be somewhat abused to describe an asymptotic tight bound where using Big Theta Θ notation might be more factually appropriate in a given context. For example, when considering a function, all of the following are generally acceptable, but tightnesses of bound (i.e., numbers 2 and 3 below) are usually strongly preferred over laxness of bound (i.e., number 1 below).

  1. T(n) = O(n100), which is identical to T(n) ∈ O(n100)
  2. T(n) = O(n3), which is identical to T(n) ∈ O(n3)
  3. T(n) = Θ(n3), which is identical to T(n) ∈ Θ(n3).

The equivalent English statements are respectively:

  1. T(n) grows asymptotically no faster than n100
  2. T(n) grows asymptotically no faster than n3
  3. T(n) grows asymptotically as fast as n3.

So while all three statements are true, progressively more information is contained in each. In some fields, however, the Big O notation (number 2 in the lists above) would be used more commonly than the Big Theta notation (bullets number 3 in the lists above) because functions that grow more slowly are more desirable. For example, if represents the running time of a newly developed algorithm for input size, the inventors and users of the algorithm might be more inclined to put an upper asymptotic bound on how long it will take to run without making an explicit statement about the lower asymptotic bound.

Read more about this topic:  Big O Notation, Related Asymptotic Notations

Other articles related to "use in computer science":

Initial Algebra - Use in Computer Science
... To obtain the type of lists whose elements are members of set A, consider that the list-forming operations are Combined into one function, they give , which makes this an F-algebra for the endofunctor F sending to ... It is, in fact, the initial F-algebra ...

Famous quotes containing the words science and/or computer:

    There does not exist a category of science to which one can give the name applied science. There are science and the applications of science, bound together as the fruit of the tree which bears it.
    Louis Pasteur (1822–1895)

    What, then, is the basic difference between today’s computer and an intelligent being? It is that the computer can be made to see but not to perceive. What matters here is not that the computer is without consciousness but that thus far it is incapable of the spontaneous grasp of pattern—a capacity essential to perception and intelligence.
    Rudolf Arnheim (b. 1904)