Big-Θ notation: Difference between revisions

From LifeWiki
Jump to navigation Jump to search
CiteCGoLMC
Confocal (talk | contribs)
formatting
Line 1: Line 1:
{{Glossary}}
{{Glossary}}
'''Big-Θ notation''' (or '''big theta notation''') is used to describe the growth rate of a [[pattern]] when the actual formula f(t){{refn|group="notes"|t is the number of [[tick]]s that the pattern has been run}} 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.
'''Big-Θ notation''' (or '''big theta notation''') is used to describe the growth rate of a [[pattern]] when the actual formula f(t){{refn|group=note|t is the number of [[tick]]s that the pattern has been run}} 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 growth rate of the [[spacefiller]] [[max]], p(t), can be expressed as follows:
For example, the population growth rate of the [[spacefiller]] [[max]], p(t), can be expressed as follows:
Line 6: Line 6:
*p(t)=t<sup>2</sup>/4+21t/2+209, t mod 4 = 0
*p(t)=t<sup>2</sup>/4+21t/2+209, t mod 4 = 0
*p(t)=t<sup>2</sup>/4+21t/2+215, t mod 4 = 2
*p(t)=t<sup>2</sup>/4+21t/2+215, t mod 4 = 2
*p(t)=t<sup>2</sup>/4+10t+923/4, otherwise
*p(t)=t<sup>2</sup>/4+10t+923/4 otherwise


As t gets large, the term t<sup>2</sup>/4 dominates. In other words, the population of max grows like t<sup>2</sup>/4, or p(t) is Θ(t<sup>2</sup>/4) or p(t) is Θ(t<sup>2</sup>).
As t gets large, the term t<sup>2</sup>/4 dominates. In other words, the population of max grows like t<sup>2</sup>/4, or p(t) is Θ(t<sup>2</sup>/4) or p(t) is Θ(t<sup>2</sup>).


==Notes==
==Notes==
<references group=notes />
<references group=note />


==External links==
==Further reading==
* {{citeCGoLMC|section=Appendix A.3}}
* {{CiteCGoLMC|section=A.3}} Appendix A: Big-Θ Notation

Revision as of 05:33, 22 December 2022

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 growth rate of the spacefiller max, p(t), can be expressed as follows:

  • p(t)=t2/4+21t/2+209, t mod 4 = 0
  • p(t)=t2/4+21t/2+215, t mod 4 = 2
  • p(t)=t2/4+10t+923/4 otherwise

As t gets large, the term t2/4 dominates. In other words, the population of max grows like t2/4, or p(t) is Θ(t2/4) or p(t) is Θ(t2).

Notes

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

Further reading