Terms / Definitions
A method for solving recurrences of the form:
T(n) = aT(n/b) + f(n)
In which there are 3 cases used to determine asymptotic bounds.
What is the Master Method?
This constant represents the number of subproblems.
What is a?
You calculate this by multiplying the height of the tree by the lowest level sum.
How do you calculate Omega from a recursion tree? aka lowest bound
T(n) = \Omega(height*lowest costing level)
These are the steps for using the substitution method and what is the expected template in homework.
1. Guess the form of the solution.
2. Use induction to find the constants and show solution works: (a) Goal (b) Base case (c) Induction step: Inductive Hypothesis.
These are the steps for writing a proof.
What are these steps part of...?
In correct order: Lemma, Proof, Algorithm, Justification, Details, Runtime
A method for solving recurrences. We guess a bound and then use mathematical induction to prove our guess correct.
What is the substitution method?
This constant represents the size of the subproblem.
What is b?
You calculate this by multiplying the height of the tree by the largest level sum.
How do you calculate Big O from a recursion tree?
T(n) = O(h*largest costing level)
In order to prove for any general number of n that the c checks out.
What is the reason we perform the induction step?
This function is used to calculate the total number of leaves in the recursion function.
n^(log_b(a))
A method for solving recurrences by converting the recurrence into a tree whose nodes represent the cost incurred at various levels of the recursion.
What is the recursion tree method?
How much to spend outside recursion. Or the initial cost of the first top most node.
"This function encompasses the cost of dividing the problem and combining the results of the subproblems." - textbook
What is f(n)?
In order to generate a good guess, which can then be verified by the substitution method.
What is the best reason to use a recursion tree?
In order to find one constraint on c to make sure the constants work out initially.
What is the reason we do the base case step?
This is the requirement for case 2 in the Master Method.
What is this requirement used for...?
if f(n)=\Theta(n^(log_b(a))*log^k(n)
One of the methods for solving recurrences that uses a specific technique where it bounds summations to solve the recurrence.
What is the recursion-tree method?
This is the form of the recurrence formula that is required for using the Master Method.
What is T(n)=aT(n/b)+f(n)?
What is a node?
We get rid of this term because it's a non-recursive term that we want to specify precisely.
Why do we want to get rid of \Theta(1) in substitution?
In substitution method: when determining Big O, we perform this step in order to determine if our guessed maximum bound is correct or not.
This solution is used in the Master Method if n^(log_b(a)) < f(n).
What is T(n)=\Theta(f(n))?
This solution is used in the Master Method if n^(log_b(a)) > f(n).
What is T(n)=\Theta(n^log_b(a))?
This tool used to search sorted arrays looks more like a recursion stick instead of a recursion tree.
What is a binary search?
What is honey?
Because it always takes time for a computer to perform an algorithm, this will always be true of runtimes.
Why are runtimes of algorithms always positive?