ch1. definition

algorithm : applying a technique to a problem results in a step-by-step procedure for solving the problem.

 

problem : a question to which we seek answer

 

parameters : variables that are not assigned specific values in the statement of the problem.

 

instance : each specific assignment of values to the parameters.

solution : the answer to the question asked by the problem in that instance.

key : often each item uniquely identifies a record

input size : reasonable measure of the size of the input

time complexity : the determination of how many times the basic operation is done for each value of the input size

T(n) : defined as the number of times the algorithm does the basic operation for an instance of size n // every-case time complexity

W(n) : defined as the maximum number of times the algorithm will ever do its basic operation for an input size of n. worst time complexity

A(n) : defined as the average(expected value) of the number of times the algorithm does the basic operation for an input size of n.

B(n) : defined as the minimum number of times the algorithm will ever do its basic operation for an input size of n.

memory complexity : an analysis of how efficient the algorithm is in terms of memory

complexity function : can be any function that maps the positive integers to the nonnegative reals.

linear time algorithm : algorithms with time complexities such as n and 100n

quadratic time algorithm : algorithalgorithm : applying a technique to a problem results in a step-by-step procedure for solving the problem.

 

problem : a question to which we seek answer

 

parameters : variables that are not assigned specific values in the statement of the problem.

 

instance : each specific assignment of values to the parameters.

solution : the answer to the question asked by the problem in that instance.

key : often each item uniquely identifies a record

input size : reasonable measure of the size of the input

time complexity : the determination of how many times the basic operation is done 

for each value of the input size

T(n) : defined as the number of times the algorithm does the basic operation for an 

instance of size n // every-case time complexity

W(n) : defined as the maximum number of times the algorithm will ever do its basic operation for an input size of n. worst time complexity

A(n) : defined as the average(expected value) of the number of times the algorithm does the basic operation for an input size of n.

B(n) : defined as the minimum number of times the algorithm will ever do its basic operation for an input size of n.

memory complexity : an analysis of how efficient the algorithm is in terms of memory

complexity function : can be any function that maps the positive integers to the nonnegative reals.

linear time algorithm : algorithms with time complexities such as n and 100n

quadratic time algorithm : algorithms with time complexities such as n^2

pure quadratic : contains no linear terms

complete quadratic :  contains linear terms

complexity categories : this means that (order) separates complexity functions into disjoint sets. we’ll call these sets complexity categories. //set of pure complexity functions that order(n), order(n^2), order(n^3)…

big O : asymptotic upper bound

omega : asymptotic lower bound

order : asymptotic tight bound

small o :…

 

divide-and-conquer approach : same strategy on an instance of a problem. top-down approach

tail-recursion : no operations are done after the recursive call

two-way merging : combining two sorted arrays into one sorted array

in-place sort : sorting algorithm that does not use any extra space beyond that needed to store the input.

we use Strassen’s method up to a threshold value of m and use the standard algorithm after reaching the threshold.

 ms with time complexities such as n^2

pure quadratic : contains no linear terms

complete quadratic :  contains linear terms

complexity categories : 

big O : asymptotic upper bound

omega : asymptotic lower bound

order : asymptotic tight bound

small o :…

 

divide-and-conquer approach : same strategy on an instance of a problem. top-down approach

tail-recursion : no operations are done after the recursive call

two-way merging : combining two sorted arrays into one sorted array

in-place sort : sorting algorithm that does not use any extra space beyond that needed to store the input.

we use Strassen’s method up to a threshold value of m and use the standard algorithm after reaching the threshold.