GATE CSE
First time here? Checkout the FAQ!
x

User iarnav

Member for: 1 year (since Oct 30, 2015)
Type: Registered user
Full name:
GATE Year:
GATE Rank:
Website:
About:
Resume:
DBLP Link:
Following standard books/videos?:
Current City: localhost
Home State:

Activity by iarnav

Score: 3,437 points (ranked #163)
Title: Loyal
Exams Created: 0
Exams Taken: 0
No. of Edits: 18
Posts: 5
Questions: 145 (47 with best answer chosen)
Answers: 5
Comments: 242
Voted on: 7 questions, 160 answers
Gave out: 167 up votes, 0 down votes
Received: 100 up votes, 2 down votes

Wall for iarnav

Hi iarnav.Let's take it up in discussion here. You might be knowing about the various design strategies such as Divide and Conquer,Greedy and Dynamic Programming. There are certain classes of problems which are classified under these. Out of them, a recurrence relation is used as a solution for those algorithms/problems which belongs to Divide and Conquer Design Strategy. This is the basis behind the use of recurrence relation. For example Merge Sort, Binary Search, Quick Sort. A Divide and conquer strategy is where a problem P is divided into subproblems. Then these sub-solutions are combined to get the original Problem P. A recurrence relation takes the following form: T(n)=
aT(n/b)+D(n)+C(n). Here a is the total no of subproblem. And b is the no of subproblems in a given subproblem. Here D(n) is the time it takes to divide a subproblem and C(n) is the time it takes to combine the solution. Thus Recurrence Relation gives us the time complexity of those classes of problems which belongs to the Divide and Conquer Design strategy.Yeah. :).
Coming up with the methods which are used to solve these recurrence relations are mentioned as under:
1)Substitution Method
2)Master's Theorem
3)Akrabazzi Method
4)Extended Masters Theorem
This covers the fundamental aspect as to why a recurrence relation is used. My advice to u: First take up sample questions for practice sake, Learn how to solve. Then some of those problems which I mentioned derive a recurrence relation for them(Merge Sort, Binary Search, Quick Sort). I hope you're satisfied now. Sir Arjun and Sir Bikram has already mentioned the further sources which u should consult to gain a deeper insight. Yeah. :). Please don't say Thanks. Okays iarnav. :). Still not able to understand then let's take the discussion here itself. Happy Learning!!
May 26 by Devshree Dubey  

Badges

Bronze

Verified Human x 1
Nice Question x 15
Notable Question x 72
Regular x 1
100 Club x 1
Grateful x 1
Dedicated x 1
Editor x 1
Asker x 1
Photogenic x 1
Reader x 1
Commenter x 1
Voter x 1

Silver

Popular Question x 20
Good Question x 1
Old-Timer x 1
Respectful x 1
1,000 Club x 1
Devoted x 1
Questioner x 1
Avid Reader x 1
Copy Editor x 1
Commentator x 1

Gold

Famous Question x 1
Ancestor x 1
Great Question x 1
26,239 questions
33,805 answers
80,214 comments
31,159 users