Verification of recurrence relation solution

Page 1 of 1

3 Replies - 1808 Views - Last Post: 25 November 2010 - 07:47 PM

#1 Guest_Parth*


Reputation:

Verification of recurrence relation solution

Posted 23 November 2010 - 08:55 PM

Hello all,

I have a recurrence relation of the form T(n) = 2T(n/2) + THETA(n), T(1) = THETA(1). I attempted to prove T(n) <= knlgn by substitution method. I give the solution below. I am VERY new to this so do not know if this is the correct way to go :)

T(n) = 2T(n/2) + cn
Assumption: T(n) <= knlgn 

Base case:
Let T(1) = c
Taking the base case as n = 2, we have 
T(2) = 2T(1) + 2c
     = 4c

For n=2, knlgn = k2lg2 = 2k

Therefore, for base case of n = 2, T(n) <= knlgn for all n >= 2, c >= 1 and k >= 2, c < k

Assumption: T(n/2) <= kn/2lgn/2
T(n) <= 2kn/2lgn/2 + cn
      = knlgn/2 + cn
      = knlgn - knlg2 + cn
      = knlgn - kn + cn
     <= knlgn for all n >= 2, c >= 1 and k >= 2, c < k


The math on this works out correctly as long as i keep c < k

Is This A Good Question/Topic? 0

Replies To: Verification of recurrence relation solution

#2 mostyfriedman   User is offline

  • The Algorithmi
  • member icon

Reputation: 729
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Verification of recurrence relation solution

Posted 23 November 2010 - 09:24 PM

hmmm this isn't how you do substitution

the recurrence is equal to nlg n though
Was This Post Helpful? 0
  • +
  • -

#3 Guest_Parth*


Reputation:

Re: Verification of recurrence relation solution

Posted 24 November 2010 - 08:11 PM

View Postmostyfriedman, on 23 November 2010 - 08:24 PM, said:

hmmm this isn't how you do substitution

the recurrence is equal to nlg n though



Then I am quite confused. There is also an "iterative" method where you repeatedly substitute subsequent expressions in the recurrence until you can extract a general form. However, this substitution is from Coreman's book and uses induction.
Was This Post Helpful? 0

#4 Nikitin   User is offline

  • D.I.C Regular

Reputation: 56
  • View blog
  • Posts: 264
  • Joined: 02-August 10

Re: Verification of recurrence relation solution

Posted 25 November 2010 - 07:47 PM

View Postmostyfriedman, on 23 November 2010 - 09:24 PM, said:

hmmm this isn't how you do substitution

the recurrence is equal to nlg n though


That's exactly how you do the substitution. Assume the answer is correct, prove it with induction.

Parth, just a few points to polish your proof.

1. The base case can be left at T(1), since everything else will depend on it.
2. Explicitly point out that you're using strong induction. In other words, in your hypothesis, you assume that T(x) <= knlgn for all x = 1 .. p. Now prove it for T(p+1).

Everything else seems correct.
Was This Post Helpful? 0
  • +
  • -
Page 1 of 1