My Math Forum Need help finishing up with solving a recurrence

 Computer Science Computer Science Forum

 October 9th, 2012, 04:50 PM #1 Member   Joined: Sep 2009 Posts: 71 Thanks: 0 Need help finishing up with solving a recurrence I'm attempting to solve a recurrence in my algorithms course in which I'm required to use a previous technique that we used in class(analysis of Randomized Quicksort) I am having a hard time grasping recurrences but I am slowly making some progress in understanding how to handle them. $T(n)= n + 1 + \frac{1}{n^2} \sum_{k = 1}^{n-1}(2k+1)T(k)$ for $n=>= 2$ multiplying by $n^2$gives $n^2T(n)= n^3 + n^2 + \sum_{k = 1}^{n-1}(2k+1)T(k)$ subtracting previous (term?) $(n-1)^2T(n-1)= (n-1)^3 + (n-1)^2 + \sum_{k = 1}^{n-1}(2k+1)T(k)$ results in$n^2T(n) - (n-1)^2T(n-1)= 3n^2 - 3n + 1 + 2n -1 + (2n-1)T(n-1)$ which should simplify to $n^2T(n) - n^2T(n-1)= 3n^2 - n$ dividing by n^2/rearranging gives$T(n)= T(n-1) + 3 - \frac{1}{n}$ $= T(n-2) + 3 - \frac{1}{n-1} + 3 - \frac{1}{n}$ $= T(n-3) + 3 + 3 + 3 - [\frac{1}{1} + \frac{1}{2} + ... + \frac{1}{n}]$ $= T(1) + \sum_{k=1}^{n-2}3 - H_n$ This is where I got so far. I don't want to make any conclusions about the running time until I verify that I am on the right track. Any advice would be appreciated. Thanks.
 October 10th, 2012, 05:48 AM #2 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Re: Need help finishing up with solving a recurrence I don't think what you have is right, since H_n ~ log n and so the limit of the sum is $-\infty.$

 Tags finishing, recurrence, solving

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post One Real Analysis 2 June 17th, 2013 01:20 PM restin84 Computer Science 1 October 5th, 2012 12:04 AM restin84 Computer Science 4 September 19th, 2012 08:01 AM hayood Computer Science 1 January 31st, 2011 12:52 PM mrbobbles Applied Math 1 May 9th, 2009 11:28 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top