Solved

# having trouble with recurrence relation

Posted on 2006-05-08
199 Views
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

0
Question by:warriorfan808

LVL 45

Accepted Solution

you are halfway through !!!!

>M(1) = 1 <---No multiplications when n = 1
>Assume that the basic operation is multiplication.

T(n) = O(1)  for  n=1

For n=2, note that inner most loop will execute 2*2 times and this would be followed by a call to Function(1)
For n=3, inner most loop will execute 3*3 times and this would be followed by a call to Function(2) ...

i.e. ...
T(n) = O(n^2) + T(n-1)  for n>1

this gives you your required recurrence relation
0

LVL 1

Author Comment

Thanks for the help sunnycoder.  Do you know of any links I can go to so I can see more examples of how this is done.  Man, you must be a whiz at algorithms.
0

LVL 45

Expert Comment

www.math.uvic.ca/faculty/gmacgill/guide/deriving.pdf

deriving recurrence relations
recurrence relations examples
0

## Featured Post

### Suggested Solutions

starOut java challenge 95 153
debug as  junit test 4 56
canBalance challenge 34 55
wordappend challenge 8 45
There is an easy way, in .NET, to centralize the treatment of all unexpected errors. First of all, instead of launching the application directly in a Form, you need first to write a Sub called Main, in a module. Then, set the Startup Object to thâ€¦
This article is meant to give a basic understanding of how to use R Sweave as a way to merge LaTeX and R code seamlessly into one presentable document.
The viewer will learn how to implement Singleton Design Pattern in Java.
This theoretical tutorial explains exceptions, reasons for exceptions, different categories of exception and exception hierarchy.