Question

how to solve a recurreance relation?? i need to learn from basic of solving recurreance relation any good material to study that??

Answer 1

it depends on the type of recurrence: linear / nonlinear, homogenous / not, order, etc. are you in a combinatorics class?

Answer 2

no i am not in combinatorics class.. is there any material study each type??

Answer 3

i will try to find something. if you have any specific questions, just ask though :).

Answer 4

ya . i need to solve recurreance equation of quicksort and binary search tree....??

Answer 5

fun....

there is a master theorem for
T(n) = aT(n/b) + cn^d
that is already proven and solved. can you use that?

you should post the actual question otherwise i can't really specifically help you.

Answer 6

generally what you'll want to do is just keep "telescoping" or plugging in the recurrence until you can get a pattern and right it as a sum.

from there it helps if the sums can be solved. are you learning about big Oh?

Answer 7

ya learning big oh , theta and omega........

Answer 8

is this a good material

pages.pacificcoast.net/~cazelais/222/rec.pdf

Answer 9

yea that looks nice. are you trying to do it from a mathematical perspective or computer science? i have some comp sci materials but it is more about big Oh then it is actually solving a recurrence. (it is more theoretical)

Answer 10

i need to solve it from comp sci perspective
?

Answer 11

i'm taking this class right now ;) but it is a really good class. very difficult though.

there are some lecture pdfs here:
http://www.cc.gatech.edu/~venkat/3510/lectures.html

attached is a sample test with questions and solutions (i took the real thing today. wowie.)

Answer 12

ya very very thanks ..... i will see through this material and say u.............

Answer 13

how can i contact u specifically? any official email id??????????????

Answer 14

no sorry. i am often on here though. i am a developer with OpenStudy :)

Answer 15

you can also try the Computer Science study group. there are a lot of similar questions.

Answer 16

oh right. then i will get u through this(open study) itself.

Answer 17

http://openstudy.com/groups/computer+science

Answer 18

ya

Answer 19

one more question is there any relation between fraction and logarithm??