| 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 | |
|
Big O notation is a , it is usually used to characterize the residual term of a truncated Infinite Series , especially an Asymptotic Series , and in Computer Science , it is useful in the Analysis of the Complexity of Algorithm s. It was first introduced by German Number Theorist Paul Bachmann in 1894, in the second volume of his book ''Analytische Zahlentheorie'' (the first volume of which came out in 1892, and did not contain big O notation). 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 capital letter O is also used, but never the digit Zero . USES 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. 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''n'' + 2. As ''n'' grows large, the ''n''² term will come to dominate, so that all other terms can be neglected—for instance when ''n'' = 500, the term 4''n''² is 1000 times as large as the 2''n'' term, and so 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 2''n''. Even if ''T''(''n'') = 1,000,000''n''², 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 Big O notation captures what remains: we write : and say that the algorithm has ''order of n2'' time complexity. Infinitesimal asymptotics Big O can also be used to describe the error term in an approximation to a mathematical function. For example, : expresses the fact that the error (the difference ) is smaller in Absolute Value than some constant times ''x''3 if ''x'' is close enough to 0. FORMAL DEFINITION Suppose and are two functions defined on some subset of the Real Number s. We say : if and only if | ||
| :<math> 6x^4 - 2x^3 + 5 \le 13 \,x^4 \,</math>                       Where C | 13 in this example |
|
| { Border | "1" cellpadding="4" cellspacing="0" |
|
| { Border | "1" cellpadding="4" cellspacing="0" |
|
| It Is Often Useful To Bound The Running Time Of | "http://wwwinformationdelightinfo/encyclopedia/entry/Graph_(data_structure)" 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 + VlgV)</math> means <math>O((E,V) \mapsto E + V\cdot\logV)</math> for a suitable metric of graphs |
|
|