Ch 5. Key Terms

Algorithm: A finite, step-by-step procedure for solving a specific problem or performing a task.

Base Case: The simplest instance of a recursive problem; the condition that terminates a recursive algorithm.

Big O Notation: An asymptotic upper bound that describes an algorithm’s worst-case growth rate.

Big Omega Notation: An asymptotic lower bound that describes an algorithm’s best-case growth rate.

Big Theta Notation: An asymptotic tight bound describing an algorithm’s exact growth rate.

Characteristic Equation: An equation derived from a linear homogeneous recurrence relation with constant coefficients, used to determine closed-form solutions.

Closed‑Form Solution: A direct formula that computes the [latex]n[/latex]th term of a sequence without recursion.

Concatenation (of Strings): The operation of joining two strings end‑to‑end to form a new string.

Decreasing Sequence: A sequence in which each term is less than the one before it.

Finite Sequence: A sequence that contains a limited number of terms.

Homogeneous Recurrence Relation: A recurrence relation with no added non-zero term; all terms depend only on previous values.

Increasing Sequence: A sequence in which each term is greater than the one before it.

Index: The position of an element within a sequence.

Index of Summation: The variable used in sigma notation to indicate which term of a sequence is being summed.

Infinite Sequence: A sequence that continues indefinitely.

Initial Conditions: Starting values of a sequence that allow a recurrence relation to generate all subsequent terms.

Iteration (Method): A technique for solving recurrence relations by expanding terms step‑by‑step to identify a pattern.

Linear Homogeneous Recurrence Relation of Order [latex]k[/latex] with Constant Coefficients: A recurrence of the form [latex]a_{n} = c_{1}a_{n-1} + c_{2}a_{n-2} + \cdots + c_{k}a_{n-k}[/latex]

Nondecreasing Sequence: A sequence where each term is greater than or equal to the one before it.

Nonincreasing Sequence: A sequence where each term is less than or equal to the one before it.

Null String (Empty String): The string with no characters, denoted [latex]\epsilon[/latex].

Pseudocode: A structured, language-neutral description of an algorithm’s logic.

Recurrence Relation: An equation that defines each term of a sequence based on one or more previous terms.

Recursive Algorithm: An algorithm that solves a problem by calling itself on smaller instances of the same problem.

Recursive Function: A function whose definition includes a call to itself.

Sequence: An ordered list of elements in which the position of each element matters.

Sigma Notation: A compact notation used to express sums using the symbol [latex]\Sigma[/latex].

String: A finite sequence of characters drawn from an alphabet.

Substring: A contiguous block of characters taken from a string.

Subsequence: A sequence obtained by selecting elements from another sequence while preserving their order.

Trace (of an Algorithm): A step-by-step record of an algorithm’s execution.