| Big O Notation |
Article Index for Big O |
Website Links For Big O |
Information AboutBig O Notation |
| CATEGORIES ABOUT BIG O NOTATION | |
| mathematical notation | |
| mathematical analysis | |
| asymptotic analysis | |
| computational complexity theory | |
|
In Computational Complexity Theory , big O notation is often used to describe how the size of the input data affects an Algorithm 's usage of Computational Resource s (usually running time or memory). It is also called '''Big Oh notation''', '''Landau notation''', and '''asymptotic notation'''. Big O notation is also used in many other scientific and mathematical fields to provide similar estimations. The symbol ''O'' is used to describe an asymptotic Upper Bound for the Magnitude of a function in terms of another, usually simpler, function. There are also other symbols ''o'', Ω, ω, and Θ for various other upper, lower, and tight bounds. Informally, the ''O'' notation is commonly employed to describe an asymptotic tight bound, but tight bounds are more formally and precisely denoted by the Θ (capital Theta ) symbol as described below. USAGE Big O notation has two main areas of application: in Mathematics , it is usually used to characterize the residual term of a truncated Infinite Series , especially an Asymptotic Series ; in Computer Science , it is useful in the Analysis of the Complexity of Algorithm s. The notation was first introduced by number theorist Paul Bachmann in 1894, in the second volume of his book ''Analytische Zahlentheorie'' ("analytic Number Theory "), the first volume of which (not yet containing big O notation) came out in 1892. The notation was popularized in the work of another German number theorist Edmund Landau , hence it is sometimes called a Landau symbol. The big-O, standing for "order of", was originally a capital Omicron ; today the identical-looking Latin capital letter '' O '' is also used, but never the digit Zero . There are two formally close, but noticeably different, usages of this notation: Infinite asymptotics and Infinitesimal asymptotics. This distinction is only in application and not in principle, however—the formal definition for the "big O" is the same for both cases, only with different limits for the function argument. Equals or member-of and other notational anomalies In a way to be made precise below, ''O''(''f''(''x'')) denotes the collection of functions ''g''(''x'') – viewed as a function of variable ''x'' – that exhibit a growth that is limited to that of ''f''(''x'') in some respect. The traditional notation for stating that ''g''(''x'') belongs to this collection is: : This is an anomalous and exceptional use of the Equals Sign in mathematics, as the above statement is not an Equation . It is improper to conclude from ''g''(''x'') = ''O''(''f''(''x'')) and ''h''(''x'') = ''O''(''f''(''x'')) that ''g''(''x'') and ''h''(''x'') are equal. One way to think of this, is to consider "= ''O''" one symbol here. To avoid the anomalous use, some authors prefer to write instead: : without difference in meaning. The common arithmetic operations are often extended to the class concept. For example, ''h''(''x'') + ''O''(''f''(''x'')) denotes the collection of functions having the growth of ''h''(''x'') plus a part whose growth is limited to that of ''f''(''x''). Thus, : expresses the same as : Another anomaly of the notation, although less exceptional, is that it does not make explicit which variable is the function argument, which may need to be inferred from the context if several variables are involved. The following two right-hand side big O notations have dramatically different meanings: : : The first case states that ''f''(''m'') exhibits polynomial growth, while the second, assuming ''m'' > 1, states that ''g''(''n'') exhibits exponential growth. So as to avoid all possible confusion, some authors use the notation : meaning the same as what is denoted by others as : A final anomaly is that the notation does not make clear "where" the function growth is to be considered; infinitesimally near some point, or in the neighbourhood of infinity. This is in contrast with the usual notation for Limit s. A similar notational device as for limits would resolve both this and the preceding anomaly, but is not in use. Infinite asymptotics Big O notation is useful when Analyzing Algorithms for efficiency. For example, the time (or the number of steps) it takes to complete a problem of size ''n'' might be found to be ''T''(''n'') = 4''n''&2 - 2''n'' + 2. As ''n'' grows large, the ''n''&2 term will come to dominate, so that all other terms can be neglected—for instance when ''n'' = 500, the term 4''n''&2 is 1000 times as large as the 2''n'' term. Ignoring the latter would have negligible effect on the expression's value for most purposes. Further, the Coefficient s become irrelevant as well if we compare to any other order of expression, such as an expression containing a term n³ or n&2. Even if ''T''(''n'') = 1,000,000''n''&2, if ''U''(''n'') = ''n''³, the latter will always exceed the former once ''n'' grows larger than 1,000,000 (''T''(1,000,000) = 1,000,000³ = ''U''(1,000,000)). So the big O notation captures what remains: we write : (pronounced "big o of n squared") and say that the algorithm has ''order of n&2'' time complexity. Infinitesimal asymptotics Big O can also be used to describe the error term in an approximation to a mathematical function. For example, : | ||
| :<math> 6x^4 - 2x^3 + 5 \le 13 \,x^4 \,</math>                       Where C | 13 in this example |
|
| { Class | "wikitable" |
|
| \sum\limits {i | 1}^{m}f_{i}(n) \in O(\max\, _{i=1}^m g_i(n) )</math> |
|
| {class | "wikitable" |
|
| It Is Often Useful To Bound The Running Time Of | "http://wwwinformationdelightinfo/information/entry/Graph_(mathematics)" class="copylinks">Graph algorithms Unlike most other computational problems, in graphs, there are two relevant parameters describing the size of the input, V and E V is the number of vertices in the graph, while E is the number of edges in the graph Inside Asymptot ic notation (and only there), it is common to use the symbols V and E, when someone really means V and E We adopt this convention here to simplify asymptotic functions and make them easily readable Keep in mind that the symbols V and E are never used inside asymptotic notation with their literal meaning, so there is no risk of ambiguity For example <math>O(E + V \log V)</math> means <math>O((E,V) \mapsto E + V\cdot\logV)</math> for a suitable metric of graphs |
|
|