having trouble with recurrence relation

Posted on 2006-05-08
Last Modified: 2012-05-05
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

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
    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.
    LVL 45

    Expert Comment


    Or search google with
    deriving recurrence relations
    recurrence relations examples

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    Enabling OSINT in Activity Based Intelligence

    Activity based intelligence (ABI) requires access to all available sources of data. Recorded Future allows analysts to observe structured data on the open, deep, and dark web.

    Suggested Solutions

    Title # Comments Views Activity
    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.

    737 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    19 Experts available now in Live!

    Get 1:1 Help Now