Big-Θ notation: Difference between revisions
Jump to navigation
Jump to search
m →Further reading: category |
|||
| Line 4: | Line 4: | ||
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: | ||
*p(t)=t<sup>2</sup>/4+21t/2+209, t mod 4 = 0 | *p(t)=t<sup>2</sup>/4+21t/2+209, [[Modular congruence|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 | ||
Revision as of 11:44, 10 April 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 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
Further reading
- Nathaniel Johnston, Dave Greene. Conway's Game of Life: Mathematics and Construction (2022), A.3. Appendix A: Big-Θ Notation