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.