Yaazh

Recurrence Relations are: Linear Recurrence  Relations Divide and Conquer Recurrences Substitution Recurrences Homogeneous Recurrences Non-Homogeneous Recurrences 1.  Linear Recurrence Relations: Following are some of the examples of recurrence relations based on linear recurrence relation. T(n) = T(n-1) + n for n > 0 and T(0) = 1 These types of recurrence relations can be easily solved using  substitution method . For example, T(n) = T(n-1) + n = T(n-2) + (n-1) + n = T(n-k) + (n-(k-1))….. (n-1) + n Substituting k = n, we get T(n) = T(0) + 1 + 2+….. +n = n(n+1)/2 = O(n^2) 2.  Divide and conquer recurrence relations: Following are some of the examples of recurrence relations based on divide and conquer. T(n) = 2T(n/2) + cn T(n) = 2T(n/2) + √n These types of recurrence relations can be easily solved using  Master Method . For recurrence relation: T(n) = 2T(n/2) + cn, the values of a = 2, b = 2 and k =1. Here logb(a) = log2(2) = 1 = k. Therefore, t...

Asymptotic Notations: Asymptotic Notations are mathematical tools used to analyze the performance of algorithms by understanding how their efficiency changes as the input size grows. These notations provide a concise way to express the behavior of an algorithm’s time or space complexity as the input size approaches infinity. Rather than comparing algorithms directly, asymptotic analysis focuses on understanding the relative growth rates of algorithms’ complexities. It enables comparisons of algorithms’ efficiency by abstracting away machine-specific constants and implementation details, focusing instead on fundamental trends. Asymptotic analysis allows for the comparison of algorithms’ space and time complexities by examining their performance characteristics as the input size varies. By using asymptotic notations, such as Big O, Big Omega, and Big Theta, we can categorize algorithms based on their worst-case, best-case, or average-case time or space complexities, providing valuable in...

Complexity of an Algorithm The Space and Time complexity of an algorithm can be utilized in order to determine its effectiveness. While most of us know that there are various methods for addressing any problem in programming, understanding how an algorithm works effectively and efficiently can add value to your programming. In order to determine the efficacy of a program or algorithm, understanding the way of evaluating them with the help of Time and Space Complexity can help the program perform optimally under certain conditions. Consequently, we become more efficient programmers Understanding the Algorithmic Complexity Algorithmic Complexity  is a measure of how long an algorithm would take to complete given an input of size n. If an algorithm needs to scale, it should calculate the output within a finite and practical time bound, even for large values of n. For this reason, complexity is determined asymptotically as n approaches infinity. While complexity is generally in terms o...