Engineer bro!

Mon May 02 2022 (2 weeks ago)

Engineer by mistake!

I am a software engineer by passion

Recurrence Relation

Recurrence relation is an equation that expresses the nth term of a sequence as a function of k preceding terms, for some fixed k (independent from n), which is called the order of the relation. Once k initial terms of a sequence are given, the recurrence relation allows computing recursively all the remaining terms of the sequence.

Analyzing control statements are easy because they are iterative. Many algorithms are recursive in nature and when we analyze them we get a recurrence relation for time complexity.

We get running time as a function of n(input size) and we get the running time on inputs of smaller size.
A recurrence relation recursively defines a sequence where the next term is a function of previous term.

Methods to solve recurrence relation

  1. Substitution ***

  2. Homogeneous (characteristic equation)

  3. Inhomogeneous

  4. Master Theorem ***

  5. Recurrence tree ***

  6. Intelligent guess work

  7. Change of variable

  8. Range transformations

Substitution Method

In substitution method we make guess for the solution then we use mathematical induction to prove the guess is correct or incorrect. This is the most acceptable method as it always works for any recurrence relation, although it takes too much time in calculation.

Example - 1

T(n)=T(n1)+n       equation 1T(n) = T(n-1) + n \ \ \ \ \ \ \ equation \ 1

T(n)T(n) is the time to solve instance of size n, and T(n1)T(n-1) is the time to solve instance of size n1n-1.

Replacing nn by n1n-1 and n2n-2, we can write the following equations.

T(n1)=T(n2)+n1       equation 2T(n2)=T(n3)+n2       equation 3T(n-1) = T(n-2) + n-1 \ \ \ \ \ \ \ equation \ 2 \\ T(n-2) = T(n-3) + n-2 \ \ \ \ \ \ \ equation \ 3

Substituting equation 3 in 2, we'll get equation 4 as follows:

T(n1)=T(n3)+n2+n1T(n1)=T(n3)+2n3       equation 4T(n-1) = T(n-3)+n-2+n-1 \\ T(n-1) = T(n-3) + 2n-3 \ \ \ \ \ \ \ equation \ 4

By substituting equation 4 in 1, we'll get the following equation:

T(n)=T(n3)+2n3+nT(n)=T(n3)+3n3       equation 5T(n) = T(n-3)+2n-3+n \\ T(n) = T(n-3) + 3n - 3 \ \ \ \ \ \ \ equation \ 5

From above observation we can write the general form of the equation 1 as follows.

T(n)=T(nk)+T(nk+1)+T(nk+2)+...+nT(n) = T(n-k)+T(n-k+1)+T(n-k+2)+...+n

Suppose, if we take k=nk=n then,

T(n)=T(nn)+T(nn+1)+T(nn+2)+...nT(n)=0+1+2+...nT(n)=n(n+1)2 T(n)=O(n2)T(n) = T(n-n)+T(n-n+1)+T(n-n+2)+...n \\ T(n) = 0+1+2+...n \\ T(n) = \frac{n(n+1)}{2} \\ \ \\ T(n) = O(n^2)

Example - 2

Put alt text here...

If we rewrite the equation then we'll get that,

T(n)=c2+T(n1)   eq (1)T(n) = c2 + T(n-1) \ \ \ eq \ (1)

By relpacing nn by n1n-1, we'll get the following

T(n1)=c2+T(n2)   eq (2)T(n-1) = c2 + T(n-2) \ \ \ eq \ (2)

By replacing nn by n2n-2, we'll get the following

T(n2)=c2+T(n3)   eq (3)T(n-2) = c2 + T(n-3) \ \ \ eq \ (3)

If we substitute eq (3) into eq (2), then we'll get the following

T(n1)=c2+c2+T(n3)   eq (4)T(n-1) = c2+c2+T(n-3) \ \ \ eq \ (4)

Substituting the value of eq (4) into eq (1), we'll get the following

T(n)=c2+c2+c2+T(n3)T(n)=3c2+T(n3)   eq (5)T(n) = c2+c2+c2 + T(n-3) \\ T(n) = 3c2 + T(n-3) \ \ \ eq \ (5)

From the above observation, we can write the general form of the equation as below

T(n)=kc2+T(nk)   eq (6)T(n) = kc2+T(n-k) \ \ \ eq \ (6)

Suppose if we take k=nk=n, then we could rewrite the above equation as follows.

T(n)=nc2+T(nn)T(n)=nc2+T(0)T(n)=nc2+c1T(n)=O(n)T(n) = nc2 + T(n-n) \\ T(n) = nc2 + T(0) \\ T(n) = nc2 + c1 \\ T(n) = O(n)

Master Theorem

The master theorem always yields asymptotically tight bounds to recurrences from divide and conquer algorithms that partition an input into smaller subproblems of equal sizes, solve the subproblems recursively, and then combine the subproblem solutions to give a solution to the original problem. The time for such an algorithm can be expressed by adding the work that they perform at the top level of their recursion (to divide the problems into subproblems and then combine the subproblem solutions) together with the time made in the recursive calls of the algorithm.

Suppose if we have the recurrence of the following form:

T(n)=aT(n/b)+f(n)T(n) = aT(n/b) + f(n)

The above recurrence relation constitutes of three parts. T(n)T(n) is the time taken to solve a problem of size nn, aa is the number of sub-problems, T(n/b)T(n/b) is the time required to solve a sub-problem and f(n)f(n) is the time required divide and conquer the sub-problems.

There are three cases:

  1. Case 1 : if f(n)f(n) is in O(nlogba)O(n^{ \log_ba}), i.e f(n)nlogbaf(n) \le n^{ \log_ba} then T(n)=nlogbaT(n) = n^{ \log_ba}

  2. Case 2 : if f(n)f(n) is in Θ(nlogba)\Theta(n^{ \log_ba}), i.e f(n)=nlogbaf(n) = n^{ \log_ba} then T(n)=nlogbalgnT(n) = n^{ \log_ba} \lg n

  3. Case 3 : if f(n)f(n) is in Ω(nlogba)\Omega(n^{ \log_ba}), i.e f(n)nlogbaf(n) \ge n^{ \log_ba} then T(n)=f(n)T(n) = f(n)

Example - 1

T(n)=2T(n/2)+Θ(n)T(n) = 2T(n/2) + \Theta(n)

Here, a=2,b=2a=2, b=2. So, nlogba=nn^{\log_ba}=n
Also, f(n)=Θ(n)=cnf(n)=\Theta(n)=cn.
Case 2 applies : T(n)=Θ(nlgn)T(n) = \Theta(n \lg n)

Example - 2

T(n)=T(n/2)+Θ(1)T(n) = T(n/2) + \Theta(1)

Here, a=1,b=2a=1, b=2. So, nlogba=nlog21=n0=1n^{\log_ba}=n^{\log_21}=n^0=1
Also, f(n)=Θ(1)=1f(n)=\Theta(1)=1.
Case 2 applies : T(n)=Θ(logn)T(n) = \Theta(\log n)

Example - 3

T(n)=4T(n/2)+nT(n) = 4T(n/2)+n

Here, a=4,b=2a=4, b=2. So, logba=2\log_ba=2 and nlogba=n2n^{\log_ba}=n^2

f(n)=nf(n) = n
So, f(n)n2    f(n) is O(nlogba)f(n) \le n^2 \implies f(n) \ is \ O(n^{\log_ba})
Case 1 applies : T(n)=Θ(n2)T(n) = \Theta(n^2)

Recurrence Tree Method

In recurrence tree method, each node represents the cost of a single sub-problem in the set of recursive function invocations. We sum the cost within each level of the tree to obtain a set of per level cost.

We sum the per level cost in-order to determine the total cost of the all levels of the recursion.

Here while solving the problem, we divide the problem into sub-problems of equal size.

E.g,

T(n)=aT(n/b)+f(n)T(n) = aT(n/b) + f(n)

where a>1,b>1a>1, b>1 and f(n)f(n) is a given function.

f(n)f(n) is the cost of splitting and combining the sub-problems.

Tree Image

In the above diagram, a problem of size n has been divided into two sub-problems of size n/bn/b.

Example

T(n)=2T(n/2)+nT(n) = 2T(n/2) + n

The recurrence tree for this recurrence is:
Recurrence Tree Method of Algorithm Analyzing

When we add the values across the levels of the recursion tree, we get a value of n for every level. The bottom level has 2logn2^{\log n} nodes and each contributing of T(1)T(1).

We have n+n+n+...n timesn+n+n+...n \ times
So,

T(n)=i=0log2n1n+2lognT(1)T(n)=nlogn+nT(n)=O(nlogn)T(n) = \sum_{i=0}^{\log_2n-1} n+2^{\log n} T(1) \\ T(n) = n \log n + n \\ T(n) = O(n \log n)

Conclusion

We have seen what are the recurrence relations and popular methods to solve them. We have also seen some examples for each method.

AlgorithmsData StructureDesign And Analysis of Algorithms

Comments (0)

Discussions (0)


© 2021 dsabyte. All rights reserved