Recurrence Flashcards
what is recurrence?
Its an equation or inequality that describes function in terms of smaller inputs.
where recurrence is used?
to represent algorithm that contains recurrsive call
what is inductive hypothesis?
its part of mathematical induction to establisth truth for cases.
give me example for inductive hypothesis
consider you want to prove certain statement is true. choose some property n=k of a statement then we need to prove n=k+1 also true using inductive hpothesis.
what are the steps of mathematical induction?
1.Base case- prove first for small values.
2.Inductive hypotheis- assume n=k for arbitrary values.
3.Inductive steps- using above hypothesis prove it for all a n vlaues.
do you think where recurrence is used in algorthims specially
it is used in divide and conquer algortihm, for to prove to algorithm correctness.
what are the ways we can solve reccurence?
In four ways, 1.substitution method. 2. recursive tree method 3. master theroem 4. Akra-Bazzi method
explain subsitution method.
In this method guess the solution and then prove use indution.
consider reccurece relation equation of megre sort
T(n)=2T(n/2)+n, we know the solution is nlogn. first we need to prove for base cases n=1,
T(1)=1 log 1,
T(1)= Big O(0)=1
now 1=1,proved.
we need to prove furthur using inductive steps assume at k ,is complying equation and finall we can conclude
can we make good guess in subsitution method?
some times we cannot make good guess,so we can use recurrence tree method to find solution and then using subistuion method to prove it.
Explain reccurrence tree method.
In this method, we divide the problem as recurrsive tree,combine each level of the tree to form solution
conside equation of merge sort. we will prove using reccurrence tree method.
T(n)=2T(n/2)+O(n)
refernece daigram https://texample.net/merge-sort-recursion-tree/
Explain master theorem,
The theorem invented by author of the book, it provide straight forward way to solve the reccurrence. instead of iteariton or expansion.
T(n)=aT( n/b )+f(n)
T(n): The time complexity of a problem of size n.
a: The number of subproblems that the problem is divided into.
𝑛/𝑏 : The size of each subproblem (assuming the problem is divided into equal-sized subproblems)
f(n): The cost outside of the recursive calls, often representing the work done to divide the problem and combine the results of subproblems
Explain cases of master theroem,
Apply three cases to resolve the recurrence.
Case 1:
𝑓(𝑛) is smaller than 𝑛log𝑏^a
Time complexity is = theta(𝑛^log𝑏^a)
Case 2:
𝑓(𝑛) is smaller than 𝑛^log𝑏^a
Time complexity is = theta(𝑛^log𝑏^a log n)
Case 3:
𝑓(𝑛) is larger than 𝑛log𝑏^a
Time complexity is = theta f(𝑛)
