Θ

(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.
graph showing relation between a function, f, and the limit function, g

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.

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 Fri Dec 17 12:49:45 2004.
HTML page formatted Wed Oct 26 09:47:07 2005.

Cite this as:
Paul E. Black, "Θ", from Dictionary of Algorithms and Data Structures, Paul E. Black, ed., NIST.
http://www.nist.gov/dads/HTML/theta.html