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.
>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) ...
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.
Or search google with
deriving recurrence relations
recurrence relations examples
0
Featured Post
December’s Course of the Month is now available! Enroll to learn ITIL® Foundation best practices for delivering IT services effectively and efficiently.
>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