Algorithms and Complexity Flashcards
A procedure for solving a problem that consists of input, output and a finite sequence of steps that converts the input to the output
Algorithm
The average number of comparisons or arithmetic operations needed when a problem is solved using the algorithm
average case time complexity
of an algorithm
f = O(g); there exists a positive constant C and a positive integer k such that f(n) <= Cg(n) for every integer n >= k
big-O
f=Q(g): there exists a positive constant C and a positive integer k such that f(n) <= Cg(n) for every integer n>= k
big-theta
an algorithm that determines whether a specified number is one of the numbers in a sequence of distinct numbers by successfully dividing the sequence in half
Binary Search
an algorithm that sorts the terms in a sequence of numbers listed in a column, so that the largest numbers successively flow to the bottom, resulting in a nondecreasing sequence
Bubble Sort
the amount of space and time needed to execute the algorithm
complexity of an algorithm
time complexity of an algorithm is O(1)
constant time complexity
an algorithm that sorts the terms in a sequence of numbers so that the terms are successfully inserted in a place in the sequence until a nondecreasing sequence results
Insert sort algorithm
An algorithm that determines whether a specified number appears in a sequence by successively proceeding through the sequence term by term
Linear search algorithm
the time complexity of the algorithm is O(n)
linear time complexity
An algorithm that sorts the terms in a sequence of numbers by successively dividing the sequence and the resulting subsequences in half and them merging the sorted subsequences until a nondecreasing sequence results
Merge sort algorithm
time complexity of the algorithm is Q(f(n)) for some polynomial f(n)
Polynomial time complexity
time complexity of the algorithm is O(n^2)
quadratic tie complexity
the amount of space required by a given algorithm to solve a problem
time complexity
the maximum number of comparisons or arithmetic operations that can occur when a problem is solved using the algorithm
worst case time complexity
the expansion of a positive integer n in base b, where b >= 2 and n = a_k * b^k + a_k-1 * b^k+1 + . . . + a_1 * b + a_0 * b^0
base b expansion
the expansion of an integer in base 2
binary expansion
a decryption technique in which each letter in the plaintext is replaced by a letter obtained by rotating the letter a fixed number of positions
Ceaser shift
an integer that divides both a and b
common divisor
of a and b
an integer that is multiple of a and b
common multiple
of a and b
an integer greater than 1 that is not prime
composite
a == b (mod n): n | (a-b)
congruence
a is congruent to b modulo n
the study of sending and receiving secret messages
cryptography
the study of systems for secure communications
cryptology
systems for secure communications
cryptosystem
a function that is one-to-one and onto
bijective function
|A| = |B|
two sets A and B have the same cardinality
Cardinalities of two sets
the smallest integer greater than or equal to x
ceiling function
the set B where f is a function from A to B
codomain
a+bi for some real numbers a and b where I = sqrt(-1)
complex number
g of f: for functions f : A -> B and g: B-> C, the composition g of f: A-> C is the function defined by g(f(x)) for each x subset A
composition
a consequence of another result
corollary
a set A such that |A| = |N|
denumerable set (countably infinite set)
the set A where fi s a function from A to B
domain
the set of all elements in A that is related to a by R
equivalence class resulting from an equivalence relation R on A, |a|
a reflexive, symmetric, and transitive relation on a set
equivalence relation
the largest integer less than or equal to x
floor function
an assignment of a unique element of B to each element of A
function (from A to B) f: A -> B
the set of points (x,y) in the Cartesian plane for which x subset A, y subset B, and y = f(x)
graph
b is an image of a under f: b = f(a)
image
a function from A to B such that distinct elements of A have distinct images in B
injective function
one-to-one
a bijective function
one-to-one correspondence
a function from A to B such that distinct elements of A have distinct images in B
one-to-one function
a function from A to B such that every element of B is the image of some element of A
onto function
a bijective function from A to A
permutation
on a nonempty set A
the set of all images of f
range
a relation R on a set S is reflexive if (a, a) subset R for all a subset S
reflexive
a R b: a is related to b by the relation R if (a, b) subset R.
a !R b: a is not related to b by the relation R if (a, b) !subset R
related to
a subset of A x B
relation (from set A to set B
a relation from S to S or a subset of S x S
relation (on a set S)
a function from A to B such that every element of B is the image of some element of A
surjective function
surjection
a relation R on a set S is symmetric if (a, b) subset R,
then (b, a) subset R for all a, b, subset S
symmetric
a relation R on set S is transitive if (a, b) subset R and (b, c) subset R, then (a, c) subset R for all a, b, c subset S
transitive
a set that is not countable
uncountable set
