Time Complexity of Recursive Algorithm
In the previous post, we have seen the complexity analysis of iterative algorithms. Here, we will do the complexity analysis of recursive algorithms. Recursion is a process in which a function call itself directly or indirectly. A(n) { If() return (A(n/2)+A(n/2)) } The above function has two recursive call in return statement of the program and a one conditional check if statement. Hence, the recursive relation for this algorithm will be. T(n)=C+2T(n/2) Here, C represent the constant time taken to check the if condition, and 2T(n/2) is the two recursive calls. To solve the recursive relation of the given algorithm, we have three methods 1> Back Substitution 2> Tree Method 3> Masters Method. Back Substitution method Example: A() { if(n>1) return (A(n-1)) } Before writing the recursive relation for the following algorithm, we will see the stopping if condition of the algorithm. if (n>1), than the recursive call ke