Recurrence Relations

-

Recurrence Relations are:

  1. Linear Recurrence Relations
  2. Divide and Conquer Recurrences
  3. Substitution Recurrences
  4. Homogeneous Recurrences
  5. 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, the complexity will be Θ(nlog2(n)).
Similarly for recurrence relation T(n) = 2T(n/2) + √n, the values of a = 2, b = 2 and k =1/2. Here logb(a) = log2(2) = 1 > k. Therefore, the complexity will be Θ(n).

3. Substitution Recurrences:

Sometimes, recurrence relations can’t be directly solved using techniques like substitution, recurrence tree or master method. Therefore, we need to convert the recurrence relation into appropriate form before solving. For example,

T(n) = T(√n) + 1

To solve this type of recurrence, substitute n = 2^m as:

T(2^m) = T(2^m /2) + 1
Let T(2^m) = S(m),
S(m) = S(m/2) + 1

Solving by master method, we get

S(m) = Θ(logm)
As n = 2^m or m = log2(n),
T(n) = T(2^m) = S(m) = Θ(logm) = Θ(loglogn)

4. Homogeneous Recurrence Relations:

A homogeneous recurrence relation is one in which the right-hand side is equal to zero. Mathematically, a homogeneous recurrence relation of order k is represented as:

with the condition that the above equation equates to 0.

Example: 

Comments

Post a Comment

Popular posts from this blog

Operating System Structure

-
Image
M.Sarulatha Monolithic System  or Simple System: A monolithic system structure refers to a software architecture where all components are tightly integrated into a single, self-contained unit. This means that the entire system is built as a single executable file, with all functionality and data stored within it. Characteristics of Monolithic Systems: 1. Tight Coupling: Components are heavily interconnected and interdependent. 2. Single Executable: The entire system is built into a single executable file. 3. Centralized Data: Data is stored within the single executable or in a centralized database. 4. No External Dependencies: The system does not rely on external services or components. Advantages of Monolithic Systems: 1. Simple to Develop: Easier to build and test, as everything is self-contained. 2. Fast Deployment: Quicker to deploy, as only a single executable needs to be deployed. 3. Easy Maintenance: Simpler to maintain, as all components are within a single codebase. Disa...
Read more

Asymptotic Notations

-
Image
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...
Read more

ASP.NET Events Handling

-
Image
  ASP.NET  Events Handling M.SARULATHA Assistant Professor Dept. of CA,JJC.           ASP.NET provides important feature event handling to Web Forms. It let us to implement event-based model for our application. As a simple example, we can add a button to an ASP.NET Web Forms page and then write an event handler for the button's click event. ASP.NET Web Forms allows events on both client and server sides.           In ASP.NET Web Forms pages, however, events associated with server controls originate on the client but are handled on the Web server by the ASP.NET.           ASP.NET Web Forms follow a standard .NET Framework pattern for event-handler methods. All events pass two arguments: an object representing the object that raised the event, and an event object containing any event-specific information. Example: Creating Event Hand...
Read more