# Solving Recurrences

Solving Recurrences – Analysis of Algorithm -Many algorithms are recursive in nature. When we analyze them, we get a recurrence relation for time complexity

We discussed analysis of loops. Many algorithms are recursive in nature. When we analyze them, we get a Solving Recurrences relation for time complexity. We get running time on an input of size n as a function of n and the running time on inputs of smaller sizes. For example in Merge Sort, to sort a given array, we divide it in two halves and recursively repeat the process for the two halves. Finally we merge the results. Time complexity of Merge Sort can be written as T(n) = 2T(n/2) + cn. There are many other algorithms like Binary Search, Tower of Hanoi, etc.

There are mainly three ways for solving recurrences.

1) Substitution Method: We make a guess for the solution and then we use mathematical induction to prove the the guess is correct or incorrect

[pastacode lang=”c” manual=”For%20example%20consider%20the%20recurrence%20T(n)%20%3D%202T(n%2F2)%20%2B%20n%0A%0AWe%20guess%20the%20solution%20as%20T(n)%20%3D%20O(nLogn).%20Now%20we%20use%20induction%0Ato%20prove%20our%20guess.%0A%0AWe%20need%20to%20prove%20that%20T(n)%20%3C%3D%20cnLogn.%20We%20can%20assume%20that%20it%20is%20true%0Afor%20values%20smaller%20than%20n.%0A%0AT(n)%20%3D%202T(n%2F2)%20%2B%20n%0A%20%20%20%20%3C%3D%20cn%2F2Log(n%2F2)%20%2B%20n%0A%20%20%20%20%3D%20%20cnLogn%20-%20cnLog2%20%2B%20n%0A%20%20%20%20%3D%20%20cnLogn%20-%20cn%20%2B%20n%0A%20%20%20%20%3C%3D%20cnLogn%0A” message=”” highlight=”” provider=”manual”/]

2) Recurrence Tree Method: In this method, we draw a recurrence tree and calculate the time taken by every level of tree. Finally, we sum the work done at all levels. To draw the recurrence tree, we start from the given recurrence and keep drawing till we find a pattern among levels. The pattern is typically a arithmetic or geometric series.

[pastacode lang=”c” manual=”For%20example%20consider%20the%20recurrence%20relation%20%0AT(n)%20%3D%20T(n%2F4)%20%2B%20T(n%2F2)%20%2B%20cn2%0A%0A%20%20%20%20%20%20%20%20%20%20%20cn2%0A%20%20%20%20%20%20%20%20%20%2F%20%20%20%20%20%20%5C%0A%20%20%20%20%20T(n%2F4)%20%20%20%20%20T(n%2F2)%0A%0AIf%20we%20further%20break%20down%20the%20expression%20T(n%2F4)%20and%20T(n%2F2)%2C%20%0Awe%20get%20following%20recursion%20tree.%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cn2%0A%20%20%20%20%20%20%20%20%20%20%20%2F%20%20%20%20%20%20%20%20%20%20%20%5C%20%20%20%20%20%20%0A%20%20%20%20%20%20%20c(n2)%2F16%20%20%20%20%20%20c(n2)%2F4%0A%20%20%20%20%20%20%2F%20%20%20%20%20%20%5C%20%20%20%20%20%20%20%20%20%20%2F%20%20%20%20%20%5C%0A%20%20T(n%2F16)%20%20%20%20%20T(n%2F8)%20%20T(n%2F8)%20%20%20%20T(n%2F4)%20%0ABreaking%20down%20further%20gives%20us%20following%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cn2%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%20%20%20%20%20%20%20%20%20%20%20%20%5C%20%20%20%20%20%20%0A%20%20%20%20%20%20%20c(n2)%2F16%20%20%20%20%20%20%20%20%20%20c(n2)%2F4%0A%20%20%20%20%20%20%20%2F%20%20%20%20%20%20%5C%20%20%20%20%20%20%20%20%20%20%20%20%2F%20%20%20%20%20%20%5C%0Ac(n2)%2F256%20%20%20c(n2)%2F64%20%20c(n2)%2F64%20%20%20%20c(n2)%2F16%0A%20%2F%20%20%20%20%5C%20%20%20%20%20%20%2F%20%20%20%20%5C%20%20%20%20%2F%20%20%20%20%5C%20%20%20%20%20%20%20%2F%20%20%20%20%5C%20%20%0A%0ATo%20know%20the%20value%20of%20T(n)%2C%20we%20need%20to%20calculate%20sum%20of%20tree%20%0Anodes%20level%20by%20level.%20If%20we%20sum%20the%20above%20tree%20level%20by%20level%2C%20%0Awe%20get%20the%20following%20series%0AT(n)%20%20%3D%20c(n%5E2%20%2B%205(n%5E2)%2F16%20%2B%2025(n%5E2)%2F256)%20%2B%20….%0AThe%20above%20series%20is%20geometrical%20progression%20with%20ratio%205%2F16.%0A%0ATo%20get%20an%20upper%20bound%2C%20we%20can%20sum%20the%20infinite%20series.%20%0AWe%20get%20the%20sum%20as%20(n2)%2F(1%20-%205%2F16)%20which%20is%20O(n2)” message=”” highlight=”” provider=”manual”/]

3) Master Method:

Master Method is a direct way to get the solution. The master method works only for following type of recurrences or for recurrences that can be transformed to following type.

[pastacode lang=”c” manual=”T(n)%20%3D%20aT(n%2Fb)%20%2B%20f(n)%20where%20a%20%3E%3D%201%20and%20b%20%3E%201″ message=”” highlight=”” provider=”manual”/]

There are following three cases:
1. If f(n) = Θ(nc) where c < Logba then T(n) = Θ(nLogba)

2. If f(n) = Θ(nc) where c = Logba then T(n) = Θ(ncLog n)

3.If f(n) = Θ(nc) where c > Logba then T(n) = Θ(f(n))

How does this work?

Master method is mainly derived from recurrence tree method. If we draw Solving Recurrences tree of T(n) = aT(n/b) + f(n), we can see that the work done at root is f(n) and work done at all leaves is Θ(nc) where c is Logba. And the height of recurrence tree is Logbn.

In recurrence tree method, we calculate total work done. If the work done at leaves is polynomially more, then leaves are the dominant part, and our result becomes the work done at leaves (Case 1). If work done at leaves and root is asymptotically same, then our result becomes height multiplied by work done at any level (Case 2). If work done at root is asymptotically more, then our result becomes work done at root (Case 3).

Examples of some standard algorithms whose time complexity can be evaluated using Master Method

Merge Sort: T(n) = 2T(n/2) + Θ(n). It falls in case 2 as c is 1 and Logba] is also 1. So the solution is Θ(n Logn)

Binary Search: T(n) = T(n/2) + Θ(1). It also falls in case 2 as c is 0 and Logba is also 0. So the solution is Θ(Logn)

Notes:

1) It is not necessary that a recurrence of the form T(n) = aT(n/b) + f(n) can be solved using Master Theorem. The given three cases have some gaps between them. For example, the recurrence T(n) = 2T(n/2) + n/Logn cannot be solved using master method.

2) Case 2 can be extended for f(n) = Θ(ncLogkn)
If f(n) = Θ(ncLogkn) for some constant k >= 0 and c = Logba, then T(n) = Θ(ncLogk+1n)

## Worst Average and Best Cases

We will take an example of Linear Search and analyze it using Asymptotic analysis.We can have three cases to analyze an algorithm:Worst,Average,Best

## Space Complexity mean

Space Complexity mean – Analysis of Algorithm The term Space Complexity is misused for Auxiliary Space at many places. Following are the correct

## Time Complexity of Loop with Powers

Time Complexity of Loop with Powers- Analysis of Algorithm What is the time complexity of below function?Time complexity of above function can be written as

## NP Completeness

NP Completeness- Analysis of Algorithm – In this post,failure stories of computer science are discussed.Can all computational problems be solved by a computer

## Pseudo polynomial Algorithms

pseudo polynomial Algorithms – Analysis of Algorithm – An algorithm whose worst case time complexity depends on numeric value of input (not number of inputs)

## Java Programming-Shortest path with exactly k edges in a directed and weighted graph

Java Programming Shortest path with exactly k edges in a directed and weighted graph The graph is given as adjacency matrix representation where value