2.13. 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

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}$

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)$ (a function describing an algorithm’s steps as the size of the problem increases) of that increases the fastest as the problem gets larger

quadratic

function describing a relationship who’s highest order is a number squared

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

complex: $ax^{2} + bx + c$

worst case

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

vector

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