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

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

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
Asked:
warriorfan808
  • 2
1 Solution
 
sunnycoderCommented:
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
 
warriorfan808Author 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
 
sunnycoderCommented:
www.math.uvic.ca/faculty/gmacgill/guide/deriving.pdf

Or search google with
deriving recurrence relations
recurrence relations examples
0

Featured Post

Prep for the ITIL® Foundation Certification Exam

December’s Course of the Month is now available! Enroll to learn ITIL® Foundation best practices for delivering IT services effectively and efficiently.

  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now