Θ

(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₁, c₂, and k, such that 0 ≤ c₁g(n) ≤ f(n) ≤ c₂g(n) for all n ≥ k. The values of c₁, c₂, 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

More information

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

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