upper-case Theta

(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) = upper-case Theta (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) = upper-case Theta (g(n)) means there are positive constants c1, c2, and k, such that 0 less than or equal to c1g(n) less than or equal to f(n) less than or equal to c2g(n) for all n greater than or equal to k. The values of c1, c2, and k must be fixed for the function f and must not depend on n.

See also big-O notation, similar to, asymptotically tight bound.

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

Author: PEB

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  (paul.black@nist.gov).

Entry modified Wed Jan 2 09:25:52 2002.
HTML page formatted Thu Jan 31 13:48:08 2002.

This page's original URL is http://www.nist.gov/dads/HTML/theta.html