Big-Θ notation: Difference between revisions
{{iff}} = if and only if |
DroneBetter (talk | contribs) m Use Template:lim |
||
| Line 12: | Line 12: | ||
==Other asymptotic notations== | ==Other asymptotic notations== | ||
::''See also {{LinkWikipedia|Limit_inferior_and_limit_superior|name=Limit inferior and limit superior|nobullet=nobullet|nosuffix=nosuffix}} and {{LinkWikipedia|Big_O_notation|name=big O notation|nobullet=nobullet}}'' | ::''See also {{LinkWikipedia|Limit_inferior_and_limit_superior|name=Limit inferior and limit superior|nobullet=nobullet|nosuffix=nosuffix}} and {{LinkWikipedia|Big_O_notation|name=big O notation|nobullet=nobullet}}'' | ||
*<tt> | *<tt>{{lim|m≥n|f(m)|name=inf}}</tt>: <tt>f</tt>'s minimum over all inputs greater than or equal to <tt>n</tt>. | ||
*<tt> | *<tt>{{lim|m≥n|f(m)|name=sup}}</tt>: like <tt>inf</tt> but <tt>f</tt>'s maximum instead. | ||
Where they are defined (when limits of functions' minima and maxima exist), <tt>inf</tt> is a strictly increasing function of <tt>n</tt>, and <tt>sup</tt> a strictly decreasing one. | Where they are defined (when limits of functions' minima and maxima exist), <tt>inf</tt> is a strictly increasing function of <tt>n</tt>, and <tt>sup</tt> a strictly decreasing one. | ||
*<tt>lim | *<tt>{{lim|n->∞|f(n)|name=lim inf}}</tt>, <tt>{{lim|n->∞|f(n)|name=lim sup}}</tt>: The limit that <tt>inf</tt> and <tt>sup</tt> approach when evaluated on arbitrarily large inputs. | ||
These may be used to rigorously define the other notations. | These may be used to rigorously define the other notations. | ||
*Small O notation: <tt>f(n)</tt> is <tt>o(g(n))</tt> if <tt>f</tt>'s growth is less than <tt>g</tt>'s | *Small O notation: <tt>f(n)</tt> is <tt>o(g(n))</tt> if <tt>f</tt>'s growth is less than <tt>g</tt>'s | ||
::<tt>lim | ::<tt>{{lim|n->∞|f(n)/g(n)}} = 0</tt> | ||
*Big O notation: <tt>f(n)</tt> is <tt>O(g(n))</tt> if <tt>f</tt>'s growth is less than or equal to <tt>g</tt>'s | *Big O notation: <tt>f(n)</tt> is <tt>O(g(n))</tt> if <tt>f</tt>'s growth is less than or equal to <tt>g</tt>'s | ||
::<tt>lim | ::<tt>{{lim|n->∞|f(n)/g(n)|name=lim sup}} < ∞</tt> | ||
::The limit may be finite or zero. | ::The limit may be finite or zero. | ||
*Big omega notation: <tt>f(n)</tt> is <tt>Ω(g(n))</tt> if <tt>f</tt>'s growth is greater than or equal to <tt>g</tt>'s | *Big omega notation: <tt>f(n)</tt> is <tt>Ω(g(n))</tt> if <tt>f</tt>'s growth is greater than or equal to <tt>g</tt>'s | ||
::<tt>lim | ::<tt>{{lim|n->∞|f(n)/g(n)|name=lim inf}} > 0</tt> | ||
::The limit may be finite or infinite. | ::The limit may be finite or infinite. | ||
*Small omega notation: <tt>f(n)</tt> is <tt>ω(g(n))</tt> if <tt>f</tt>'s growth is greater than <tt>g</tt>'s | *Small omega notation: <tt>f(n)</tt> is <tt>ω(g(n))</tt> if <tt>f</tt>'s growth is greater than <tt>g</tt>'s | ||
::<tt>lim | ::<tt>{{lim|n->∞|f(n)/g(n)}} = ∞</tt> | ||
With these definitions, <tt>f(n)=Θ(g(n))</tt> {{iff}} <tt>f(n)=O(g(n))</tt> and <tt>f(n)=Ω(g(n))</tt>, in the same manner that <tt>x=y</tt> {{iff}} <tt>x≤y</tt> and <tt>x≥y</tt>. | With these definitions, <tt>f(n)=Θ(g(n))</tt> {{iff}} <tt>f(n)=O(g(n))</tt> and <tt>f(n)=Ω(g(n))</tt>, in the same manner that <tt>x=y</tt> {{iff}} <tt>x≤y</tt> and <tt>x≥y</tt>. | ||
Revision as of 23:46, 20 August 2023
Big-Θ notation (or big theta notation) is used to describe the growth rate of a pattern when the actual formula f(t)[note 1] for the growth is complex but, over time, becomes effectively the same as a simpler formula g(t). It is said that f(t) is proportional to g(t) or, even more simply, the pattern grows like g(t). This is expressed in big-Θ notation as f(t) is Θ(g(t)). In essence, g sheds details of f which might otherwise obscure understanding of what happens as t gets large.
For example, the population of the spacefiller max, p(t), can be expressed as follows:
- p(t)=t2/4+21t/2+209, if t ≡ 0 (mod 4)
- p(t)=t2/4+21t/2+215, if t ≡ 2 (mod 4)
- p(t)=t2/4+10t+923/4 otherwise
As t gets large, the t2/4 term dominates. In other words, the population of max grows like t2/4, or p(t) is Θ(t2) or p(t) is Θ(t2/4).
Other asymptotic notations
- See also Limit inferior and limit superior and big O notation at Wikipedia
- infm≥n(f(m)): f's minimum over all inputs greater than or equal to n.
- supm≥n(f(m)): like inf but f's maximum instead.
Where they are defined (when limits of functions' minima and maxima exist), inf is a strictly increasing function of n, and sup a strictly decreasing one.
- lim infn->∞(f(n)), lim supn->∞(f(n)): The limit that inf and sup approach when evaluated on arbitrarily large inputs.
These may be used to rigorously define the other notations.
- Small O notation: f(n) is o(g(n)) if f's growth is less than g's
- limn->∞(f(n)/g(n)) = 0
- Big O notation: f(n) is O(g(n)) if f's growth is less than or equal to g's
- lim supn->∞(f(n)/g(n)) < ∞
- The limit may be finite or zero.
- Big omega notation: f(n) is Ω(g(n)) if f's growth is greater than or equal to g's
- lim infn->∞(f(n)/g(n)) > 0
- The limit may be finite or infinite.
- Small omega notation: f(n) is ω(g(n)) if f's growth is greater than g's
- limn->∞(f(n)/g(n)) = ∞
With these definitions, f(n)=Θ(g(n)) iff f(n)=O(g(n)) and f(n)=Ω(g(n)), in the same manner that x=y iff x≤y and x≥y.
Notes
Further reading
- Nathaniel Johnston, Dave Greene. Conway's Game of Life: Mathematics and Construction (2022), A.3. Appendix A: Big-Θ Notation