121 Week 15 - Recursive Algorithms Complexity Flashcards
Recursive algorithm
An algorithm which calls itself with smaller input values.
It obtains the result for the current input by applying simple operations to the returned value for the smaller input.
Recurrence relation
An expression that expresses each term using previous terms. Instead of being an explicit definition for terms, it provides a rule for generating future terms.
It can be used to define a recursive algorithm.
How are recurrence relations used to find time complexity of recursive algorithms
By expressing the time complexity T(n) in terms of smaller subproblems you can solve the recurrence relations to find a closed-form complexity of the algorithm.
What are the 3 methods for evaluating the time complexity of recursive algorithms
Back Substitution, Recursion Tree, Master Theorem.
Back substitution method
[Example in square brackets]
- Define the recurrence relation. [T(n) = T(n-1) + T(1). T(1) is assumed to be 1 so: T(n) = T(n-1) + 1]
- Expand the recursive element [T(n-1) = T(n-2) + 1] and substitute it back into the previous equation [T(n) = T(n-2) + 2]
- Repeat until you can see a pattern [Expand: T(n-2) = T(n-3) + 1. Sub: T(n) = T(n-3) + 3] [Expand: T(n-3) = T(n-4) + 1. Sub: T(n) = T(n-4) + 4].
- Express the pattern for when the relation has been expanded k times [T(n) = T(n-k) + k]
- Identify the base case/ stopping condition [stops when input reaches one - when T(n) = T(1). base case: n-k = 1
- Solve the base case to find k. [k = n-1]
- Substitute k into the k expansions equation [T(n) = T(n-k) +k -> T(n) = T(1) + n-1 -> T(n) = 1+n-1 -> T(n) = n]
- Find complexity of the equation [For T(n) = n, algorithm is θ(n) complexity]
Recursion tree
A type of tree that diagrams the tree of recursive calls and the amount of work done at
each call.
How does recursion tree find time complexity
Uses a recursive tree to break down the recursion relation. At each level in the tree it finds the work done at that level.
Find an expression for how many levels the recursion tree will have for input size n.
Find the sum of all the work done: work done per level * number of levels.
Recursion tree method
[Example in square brackets]
- Define recursive relation [T(n) = 2T(n/2) + O(n)].
- Define the recursive calls and work done at each level [2T(n/2) represents two recursive calls. O(n) represents the work] done outside the recursive calls].
- The root of the tree represents T(n) - the total work for an input size n.
- Split the tree once and find the work done at that level. [T(n) -> 2 recursive calls T(n/2). Work done: O(n)].
- Continue splitting the tree and finding work done [T(n/2) -> 2 recursive calls of T(n/4). Work done: O(n)] until you can find a pattern.
- Define the general pattern for level i [at level i there are 2^i subproblems. Each subproblem has input size of n/2^i. Work done at level i is always O(n)].
- Determine the number of levels by finding the base case/stopping condition and solving for i [recursion stops when problem size is 1 - n/2^i = 1. Solve: n/2^i = 1 -> 2^i = n -> i = log2(n). Number of levels is log2(n).
- Find the total work across all levels: work done per level * number of levels [T(n) = O(n) * log2(n). Total work done: T(n) = θ(n logn)
- Total work done is the time complexity [Time complexity = θ(n logn).
Requirements to use master theorum
Function must be monotonically increasing - for a larger input size, the output must be larger than before.
Function must be in the form T(n) = aT(n/b) + f(n).
Function must satisfy:
- a ≥ 1 and a is a constant,
- b ≥ 2 and b is a constant,
- T(1) > 0
- f(n) is θ(n^d) where d ≥ 0. f(n) is a polynomial
Using master theorem
[Example in square brackets]
Define the recurrence relation. [𝑇(n/2) + 1/2n^2 + n].
Determine whether master theorem can be used for the recurrence relation.
Determine a,b and d [a=1, b=2, d=2]
Use the following rules to determine the time complexity:
- if a < b^d: T(n) = θ(n^d)
- if a = b^d: T(n) = θ(n^d logn)
- if a < b^d: θ(n^(logb(a) ) )
[1 < 2^2 so T(n) = θ(n^d) -> T(n) = θ(n^2) ]
