
Computer Science Computer Science Forum 
 LinkBack  Thread Tools  Display Modes 
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. for multiplying by gives subtracting previous (term?) results in which should simplify to dividing by n^2/rearranging gives 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 

Tags 
finishing, recurrence, solving 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Solving Recurrence equation  One  Real Analysis  2  June 17th, 2013 01:20 PM 
Need help solving(another) recurrence  restin84  Computer Science  1  October 5th, 2012 12:04 AM 
Solving a recurrence  restin84  Computer Science  4  September 19th, 2012 08:01 AM 
solving recurrence  hayood  Computer Science  1  January 31st, 2011 12:52 PM 
Solving recurrence relations with two variables  mrbobbles  Applied Math  1  May 9th, 2009 11:28 AM 