Big O, Big Omega, and Big Theta Notations

These flashcards cover essential vocabulary related to Big O, Big Omega, and Big Theta notations as discussed in the lecture.

Big O Notation

A mathematical notation used to describe the upper bound of a function's growth rate, indicating the worst-case performance.

Big Omega Notation

A mathematical notation used to describe the lower bound of a function's growth rate, indicating the best-case performance.

Big Theta Notation

A mathematical notation indicating that a function grows at the same rate as another, providing both upper and lower bounds.

Triangle Inequality

States that for any two quantities, the absolute value of their sum is less than or equal to the sum of their absolute values.

Limit as x approaches infinity

A method for analyzing the behavior of a function as the input grows larger, often used to determine growth rates of functions.

Constant Multipliers in Notation

In Big O, Big Omega, and Big Theta, constants (c and k) are used to define the bounds but are not unique; different constants can suffice for proving the same relation.

Order of Growth

A classification that describes how the running time or space requirements of an algorithm grow relative to the input size.