warriorfan808
asked on
having trouble with recurrence relation
I've been going through the book to find examples to help me do this problem, but I can't find any. Could someone help walk me through this problem or direct me to a problem on the web that is very simular to it.
Function (n: positive integer)
if n=1 then return 1
sum <- 0
for i <- 1 to n do
for j <- 1 to n do
sum <- sum - i*j
return sum + Function(n-1)
If T(n) is the run-time of Function(n) , write down a recurrence relation on and then solve the recurrence. Assume that the basic operation is multiplication.
So far I got the following:
M(1) = 1 <---No multiplications when n = 1
F(n) = Function (n-1) for every n >1
F(1) = 1
Function (n: positive integer)
if n=1 then return 1
sum <- 0
for i <- 1 to n do
for j <- 1 to n do
sum <- sum - i*j
return sum + Function(n-1)
If T(n) is the run-time of Function(n) , write down a recurrence relation on and then solve the recurrence. Assume that the basic operation is multiplication.
So far I got the following:
M(1) = 1 <---No multiplications when n = 1
F(n) = Function (n-1) for every n >1
F(1) = 1
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
www.math.uvic.ca/faculty/gmacgill/guide/deriving.pdf
Or search google with
deriving recurrence relations
recurrence relations examples
Or search google with
deriving recurrence relations
recurrence relations examples
ASKER