(definition)

**Definition:**
A theoretical measure of the execution of an *algorithm*, usually the time or memory needed, given the problem size n, which is usually the number of items. Informally, saying some equation f(n) = Θ (g(n)) means it is within a constant multiple of g(n). The equation is read, "f of n is theta g of n".

**Formal Definition:** f(n) = Θ (g(n)) means there are positive constants c_{1}, c_{2}, and k, such that 0 ≤ c_{1}g(n) ≤ f(n) ≤ c_{2}g(n) for all n ≥ k. The values of c_{1}, c_{2}, and k must be fixed for the function f and must not depend on n.

**Also known as** theta.

**Generalization** (I am a kind of ...)

*big-O notation*.

**See also**
*~*, *asymptotically tight bound*.

*Note:
This is the upper-case Greek letter Theta.*

Author: PEB

**Donald E. Knuth**, *Big Omicron and Big Omega and Big Theta*, SIGACT News, 8(2):18-24, April-June 1976.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified 14 August 2008.

HTML page formatted Thu May 31 08:47:23 2012.

Cite this as:

Paul E. Black, "Θ", in
*Dictionary of Algorithms and Data
Structures* [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 14 August 2008. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/theta.html