My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum

LinkBack Thread Tools Display Modes
October 9th, 2012, 04:50 PM   #1
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.


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.
restin84 is offline  
October 10th, 2012, 05:48 AM   #2
Global Moderator
CRGreathouse's Avatar
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
CRGreathouse is offline  

  My Math Forum > Science Forums > Computer Science

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

Copyright © 2019 My Math Forum. All rights reserved.