Big-Θ notation: Difference between revisions
Created page with "{{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 ticks that the pattern has been run}} for the growth is complex but, over time, becomes the same as a simpler formula g(t). We say 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))'''. This is u..." |
No edit summary |
||
| 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 ticks that the pattern has been run}} for the growth is complex but, over time, becomes the same as a simpler formula g(t). We say 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))'''. This is useful when the formula for f is complex and the formula for g is comparatively simple and therefore easier to understand. In essence, g sheds details of f (like scalars and lower-order algebraic terms) which might otherwise obscure our 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="notes"|t is the number of ticks that the pattern has been run}} for the growth is complex but, over time, becomes effectively the same as a simpler formula g(t). We say 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))'''. This is useful when the formula for f is complex and the formula for g is comparatively simple and therefore easier to understand. In essence, g sheds details of f (like scalars and lower-order algebraic terms) which might otherwise obscure our 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: | ||
Revision as of 22:16, 24 August 2022
Big-Θ notation (or big theta notation) is used to describe the growth rate of a pattern when the actual formula f(t)[notes 1] for the growth is complex but, over time, becomes effectively the same as a simpler formula g(t). We say 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)). This is useful when the formula for f is complex and the formula for g is comparatively simple and therefore easier to understand. In essence, g sheds details of f (like scalars and lower-order algebraic terms) which might otherwise obscure our 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 even p(t) is Θ(t2).
Notes
- ↑ t is the number of ticks that the pattern has been run
External links
- Conway's Game of Life: Mathematics and Construction, A.3 Appendix A: Big-Θ Notation