REVIEW TERMS Flashcards
Study Terms
- ) What does RAM stand for?
2. ) What is the purpose of RAM model?
- ) What does RAM stand for? - Random Access Memory
- ) What is the purpose of RAM model?
a. assumes that access to a word in memory requires 1 unit of time (generic single processor)
b. we want a metric of computation that is machine independent
c. support single constant time instruction
d. cost is uniform for all simple instruction
e. unlimited memory
f. flat memory (no memory hierarchy)
g. sequential execution - (no concurrency)
What criteria affect(s) the complexity of an algorithm?
What criteria affect(s) the complexity of an algorithm?
- a complexity of an algorithm depends on
a. size of input
b. other characteristics of input, such as partially solved
- Define worst case complexity
- Define average case complexity
- Define best case complexity
- Define worst case complexity
- The maximum steps that the algorithm
can take for ANY possible input
- Define average case complexity
- The average of the running times of ALL of the possible inputs - Define best case complexity
- The minimum number of steps for any possible input
Given LINEAR-SEARCH Algorithm
LINEAR-SEARCH (A, key)
1: i = 0 . c1
2: while i < n and A[i] != key do . c2
3: i + + . c3
4: end while
5: if i < n then . c5
6: return true . c6
7: else
8: return false . c8
What is the worst case and the best case complexity of Linear-Search?
What is the worst case and the best case complexity of Linear-Search?
Best case: if the key is the first element in the array.
T(n) = c1n + c2n + c5n + c6n
Summary: >>Line 1 number of execution = 1 unit >>Line 2 number of execution = 1 unit >>Line 5 number of execution = 1 unit >>Line 6 number of execution = 1 unit
Worst case: key is not in the array
T(n) = c1n + k
What is order of growth?
What is Asymptotic complexity?
What is complexity?
What is order of growth?
> > How running time grows with input size
What is Asymptotic complexity?
» The running time for large inputs
What is complexity?
»is denoted/dominated by the highest order term in the
expression for running time … recall that unless explicitly stated
otherwise, we are concerned with the worst time analysis of an algorithm
If the complexity of algorithm A is of a higher order than the
complexity of algorithm B, what can we say about A and B?
If the complexity of algorithm A is of a higher order than the complexity of algorithm B, what can we say about A and B?
> > we say that B is more efficient than A
Show growth rates of the following:
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < n^k where k is some constant > 2 < n!
Show growth rates of the following:
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2)
O(1) - Constant time ... • O(logn) - Logarithmic time ... • O(n) - Linear time ... • O(nlogn) linear times log(n) • O(n^2) Quadratic time • O(n^k) polynomial time • O(2^n) exponential • O(n!) factorial
What is Asymptotic Efficiency?
Define bound?
What is Asymptotic Efficiency?
> > concerned with the running time of an
algorithm as the size of the input increases without bound
Define bound?
> > A measure of ”close”ness of one property to
another
What is Recurrence equation (recurrence)?
What is Recurrence equation (recurrence)?
> > the running time for a
divide-and-conquer algorithm on input of size n, represented in terms of
the running time of the “smaller” sub problems.
What is a BST : Binary Search Tree?
What is a BST : Binary Search Tree?
A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties −
The left sub-tree of a node has a key less than or equal to its parent node’s key.
The right sub-tree of a node has a key greater than to its parent node’s key.
Thus, BST divides all its sub-trees into two segments; the left sub-tree and the right sub-tree and can be defined as −
For an unbalance tree:
What is the cost for T(n) = T(n/4) + T(3/n4) + n
For an unbalance tree:
What is the cost for T(n) = T(n/4) + T(3/n4) + n
> > • Level 0 : n → cost: n
• Level 1 : (n/4) + (3n/4) → cost: n
• Level 2 : (n/16) +(3n/1)6 +(3n/16) +(9n/16) → cost: n
T(n) = 3T(n/4) + Θ(n^2)?
What is \theta (n^2) refer to?
T(n) = 3T(n/4) + Θ(n^2)?
What is \theta (n^2) refer to?
>> The amount of work done by “each” invocation of the algorithm/function needs n 2 work (times some constant) plus the work of all recursive calls.
What is mathematical Induction?
What is mathematical Induction?
>> Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the basis) and that from each rung we can climb up to the next one (the step). – Donald Knuth
> > if P(k) is true (called induction hypothesis), then P(k + 1) is true …
in other words, if the basis step and the inductive step are proven, then
P(n) is true for all natural numbers
What is the purpose of loop invariants?
Define loop invariant?
What is the purpose of loop invariants?
> > allow for assessing correctness of an algorithm
Define loop invariant?
> > A statement about an algorithm that remains valid throughout all iterations of the algorithm
What can be said about loop invariants for:
Initialization, Maintenance, and Termination
What can be said about loop invariants for:
Initialization, Maintenance, and Termination
Initialization : the “condition” is true BEFORE the first iteration of a for loop
Maintenance : the “condition” is true AFTER each iteration and is true BEFORE each next iteration of a for loop
Termination : the “condition” is true AFTER a for loop terminates, and provides useful information about the correctness of an algorithm
