Problem Solving with Algorithms and Data Structures using C++ The PreTeXt Interactive Edition

Glossary Glossary

algorithm.

a generic, step-by-step list of instructions for solving a problem.

🔗

average case.

refers to when an algorithm performs between its worst and best case given a certain data set or circumstance.

🔗

best case.

refers to when an algorithm performs especially good given a certain data set or circumstance.

🔗

Big-O notation.

another term for order of magnitude; written as $O(f(n))$

🔗

brute force.

technique that tries to exhaust all possibilities of a problem.

🔗

contains.

A hash operation used to check if a table contains a specific element.

🔗

contiguous.

adjacent or next to.

🔗

dynamic size.

able to change size automatically.

🔗

exponential.

function represented as a number being raised to a power that increases like $f(n)=2^n$

🔗

get_item.

A hash operation used to retrieve the information associated with a hash key.

🔗

hash table.

a collection consisting of key-value pairs with an associated hash function that maps the key to the associated value.

🔗

linear.

function that grows in a one to one relationship with its input like $f(n)=n$

🔗

logarithmic.

functions that are the inverse of exponential functions usually presented as $f(n)=logn$

🔗

order of magnitude.

function describing the part $T(n)$ that increases the fastest as the value of n increases (a function describing an algorithm’s steps as the size of the problem increases).

🔗

quadratic.

function describing a relationship who’s highest order is a number squared. For instance:

🔗

simplified: $f(n)=x^2$

🔗

complex: $a{x}^2+bx+c$

🔗

set_item.

A hash operation used to add an item to your table.

🔗

vector.

sequence container storing data of a single type that is stored in a dynamically allocated array which can change in size.

🔗

worst case.

refers to when an algorithm performs especially poorly given a certain data set or circumstance.

🔗