Theoretical Algorithm Analysis Flashcards
(15 cards)
What are the basic steps for analyzing an algorithm?
- Identify critical operators
- Count operations performed
- Express number of operations as function of input size (input = n -> f(n)
- Express f(n) using Big-O Notation
What is an Average Case Analysis?
Considering all possible cases, making the appropriate assumptions for the likelihood of each case, and average the case operation numbers
What is an upper bound?
f(n) = O(g(n)), where g(n) is the largest part of f(n)
What is the tightest upper bound of:
f(n) = 1000nlogn + 3n^2 + 74n + 1/2n^3
f(n) = O(n^3)
What is the tightest upper bound of:
f(n) = 45n + n(n-1)/2 + nlogn
f(n) = O(n^2)
What is Recurrence Relation?
The function that will be substituted backwards until the Base Case is reached
What is the T(n) of an algorithm?
The number of critical operations needed to solve the problem when input is size n
What is the SIMPLIFIED T(n) of a problem?
The cost of solving one or more reduced size problems + The cost of pre/post processing
What is T(n) used for?
To find the Big-O of theoretical algorithms by figuring out the cost of the critical operations, since there is no code to analyze
What is the General Term and T(n) of this problem, given the RR and BC?
RR: T(n) = 1 + T(n - 1)
BC: T(0) = 0
RR: Recurrence Relation BC: Base Case
General Term: k + T(n-k)
T(n) = n = O(n)
What is the General Term and T(n) of this problem, given the RR and BC?
RR: T(n) = 2T(n/2) + n - 1
BC: T(1) = 0
RR: Recurrence Relation BC: Base Case
General Term: 2^kT(n/2^k) - kn
T(n) = nlog_2(n) = O(n log(n))
What is the General Term and T(n) of this problem, given the RR and BC?
RR: T(n) = 1 + T(n/2)
BC: T(1) = 1
RR: Recurrence Relation BC: Base Case
General Term: k + T(n/2^k)
T(n) = log_2(n) + 1 = O(log(n))
What is the General Term and T(n) of this problem, given the RR and BC?
RR: T(n) = n - 1 + T(n-1)
BC: T(1) = 0
RR: Recurrence Relation BC: Base Case
General Term: (n-1) + (n-2) + … + k + T(k)
T(n) = n(n-1)/2 = O(n^2)
What is the General Term and T(n) of this problem, given the RR and BC?
RR: T(n) = 2T(n - 1) + 1
BC: T(0) = 0
RR: Recurrence Relation BC: Base Case
General Term: 2^kT(n-k) + 2^k-1 + 2^k-2
+ … +2^1 + 2^0
T(n) = 2^n - 1 = O(2^n)
What can you do when trying to find the Upper/Lower bounds?
You can over estimate during substitution for the upper bound, and under estimate during substitution for the lower bound
