Big-Θ notation: Difference between revisions

From LifeWiki
Jump to navigation Jump to search
Add other asymptotic notations
m use vertical {{frac}} form for fractions (much clearer this way, I think)
 
(4 intermediate revisions by 4 users not shown)
Line 4: Line 4:
For example, the population of the [[spacefiller]] [[max]], p(t), can be expressed as follows:
For example, the population of the [[spacefiller]] [[max]], p(t), can be expressed as follows:


*<tt>p(t)=t<sup>2</sup>/4+21t/2+209</tt>, if <tt>[[Modular congruence|t ≡ 0 (mod 4)]]</tt>
*<tt>p(t) = {{frac|t<sup>2</sup>|4}} + {{frac|21*t|2}} + 209</tt>, if <tt>[[Modular congruence|t ≡ 0 (mod 4)]]</tt>
*<tt>p(t)=t<sup>2</sup>/4+21t/2+215</tt>, if <tt>t ≡ 2 (mod 4)</tt>
*<tt>p(t) = {{frac|t<sup>2</sup>|4}} + {{frac|21*t|2}} + 215</tt>, if <tt>t ≡ 2 (mod 4)</tt>
*<tt>p(t)=t<sup>2</sup>/4+10t+923/4</tt> otherwise
*<tt>p(t) = {{frac|t<sup>2</sup>|4}} + 10*t + {{frac|923|4}}</tt> otherwise<!--closed form (though probably violates the spirit of the article)
 
:<tt>p(t) = {{frac|2*t<sup>2</sup> + 82*t + 1771 - 24*cos({{frac|π*t|2}}) + (2*n-75)*cos(π*t)|8}}</tt>-->


As <tt>t</tt> gets large, the <tt>t<sup>2</sup>/4</tt> term dominates. In other words, the population of max grows like <tt>t<sup>2</sup>/4</tt>, or <tt>p(t)</tt> is <tt>Θ(t<sup>2</sup>)</tt> or <tt>p(t)</tt> is <tt>Θ(t<sup>2</sup>/4)</tt>.
As <tt>t</tt> gets large, the <tt>t<sup>2</sup>/4</tt> term dominates. In other words, the population of max grows like <tt>t<sup>2</sup>/4</tt>, or <tt>p(t)</tt> is <tt>Θ(t<sup>2</sup>)</tt> or <tt>p(t)</tt> is <tt>Θ(t<sup>2</sup>/4)</tt>.
Line 12: Line 14:
==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>inf<sub>m&ge;n</sub> (f(m))</tt>: <tt>f</tt>'s minimum over all inputs greater than or equal to <tt>n</tt>.
*<tt>{{lim|m&ge;n|f(m)|name=inf}}</tt>: <tt>f</tt>'s minimum over all inputs greater than or equal to <tt>n</tt>.
*<tt>sup<sub>m&ge;n</sub> (f(m))</tt>: like <tt>inf</tt> but <tt>f</tt>'s maximum instead.
*<tt>{{lim|m&ge;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 an increasing function of <tt>n</tt>, and <tt>sup</tt> a decreasing one.


*<tt>lim inf<sub>n->∞</sub> (f(n))</tt>, <tt>lim sup<sub>n->∞</sub> (f(n))</tt>: The limit that <tt>inf</tt> and <tt>sup</tt> approach when evaluated on arbitrarily large inputs.
*<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<sub>n->∞</sub>(f(n)/g(n))=0</tt>
::<tt>{{lim|n->∞|{{frac|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 sup<sub>n->∞</sub>(f(n)/g(n))<∞</tt>
::<tt>{{lim|n->∞|{{frac|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 inf<sub>n->∞</sub>(f(n)/g(n))>0</tt>
::<tt>{{lim|n->∞|{{frac|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<sub>n->∞</sub>(f(n)/g(n))=∞</tt>
::<tt>{{lim|n->∞|{{frac|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&le;y</tt> and <tt>x&ge;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&le;y</tt> and <tt>x&ge;y</tt>.


==Notes==
==Notes==

Latest revision as of 17:45, 14 September 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) = t24 + 21*t2 + 209, if t ≡ 0 (mod 4)
  • p(t) = t24 + 21*t2 + 215, if t ≡ 2 (mod 4)
  • p(t) = t24 + 10*t + 9234 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 an increasing function of n, and sup a 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

  1. ↑ t is the number of ticks that the pattern has been run

Further reading