[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 206

# 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

0
warriorfan808
• 2
1 Solution

Commented:
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

Author Commented:
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

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