Algorithms and Complexity - Time Complexity of Recursive Algorithms

Flashcards for reviewing time complexity of recursive algorithms, covering recursive algorithms definition, examples, and methods to evaluate time complexity such as Back Substitution, Recursion Tree, and Master Theorem.

What is a recursive algorithm?

An algorithm which calls itself with smaller input values.

When can you use a recursive algorithm?

A problem can be solved utilizing solutions to smaller versions of the same problem, and the smaller versions reduce to easily solvable cases.

In order to calculate the time complexity of a recursive function, what do we need to do?

To define its time complexity function T(n).

If Sum(1) is computed using a fixed number of operations C1, what is T(1)?

T(1) = C1

If n > 1 the function will perform a fixed number of operations C2, and in addition, it will make a recursive call to Sum(n-1). What is the total?

T(n) = C2 + T(n-1)

How can we reduce finding the time complexity of the Sum function?

Finding the time complexity of the Sum function can then be reduced to solving the recurrence relation T(1) = 1 and T(n) = T(n-1) + 1 when n > 1.

How does a recursive implementation of a Binary Search algorithm work?

Compare the mid of the search space with the key, return the index where the key is found, or call the recursive function for the next search space, halving the search space with each call.

What is the recurrence relation of the recursive binarySearch function?

T(n) = T(n/2) + 1 when n > 1 and T(1) = 1

What is back substitution in the context of recursive algorithms?

A method for finding T(n) in terms of n by repeatedly substituting T(n-1), T(n-2), etc., until a base case is reached.

What is the general formula derived from back substitution in the example provided for the Sum function?

T(n) = T(n-k) + k

How can we reduce finding the time complexity of the recursive binarySearch function?

Finding the time complexity of the recursive binarySearch function can be reduced to solving the recurrence relation T(n) = T(n/2) + 1 when n > 1 and T(1) = 1.

What is the time complexity of binary search?

The algorithm is O(log₂(n)).

What is a recursion tree and what is it useful for?

A diagram that represents the tree of recursive calls and the work done at each call, useful for visualizing recurrence iteration.

What are Trees?

Trees are special cases of graphs having no loops and only one path between any two vertices.

What is the depth of a tree?

Depth of the deepest node.

What is the branching factor of a tree?

The number of children at each node.

What is the Master Theorem?

A theorem used to solve recurrence relations of the form T(n) = aT(n/b) + f(n) under certain conditions.

Under what conditions can you NOT use the Master Theorem?

T(n) is not monotone, f(n) is not a polynomial, b cannot be expressed as a constant.