My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum


Reply
 
LinkBack Thread Tools Display Modes
November 24th, 2008, 11:40 AM   #1
Newbie
 
Joined: Nov 2008

Posts: 1
Thanks: 0

Is there any one can help me with this recurrence ??

I have this problem and I have no Idea how to solve it.

Q-" solve the following recurrence relation. (Assume n=2k ")


T(n)= { 1 n=2 ;
2 T(n/2) + (n-1) n>2 ;

Hint :" Merge Sort "

please help me with anything
Student 100 is offline  
 
November 24th, 2008, 12:52 PM   #2
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 932

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Is there any one can help me with this recurrence ??

Without knowing what tools you have, I can't tell you how you're supposed to solve it. The Master Theorem solves it directly; induction can prove an exact (not O(blah)) form for powers of 2.
CRGreathouse is offline  
November 25th, 2008, 06:52 AM   #3
Senior Member
 
Joined: Oct 2007
From: Chicago

Posts: 1,701
Thanks: 2

Re: Is there any one can help me with this recurrence ??

Quote:
Originally Posted by Student 100
(Assume n=2k ")
Should that be "assume "?

If you do that:

where t(k) = T(2^k) [=T(n)].

Doing one "iteration" gives:


Do you see this going anywhere?
cknapp is offline  
Reply

  My Math Forum > Science Forums > Computer Science

Tags
recurrence



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Recurrence equation Oscarmovies Computer Science 2 March 1st, 2013 11:54 PM
recurrence relations emosms Applied Math 1 April 22nd, 2011 03:52 AM
solving recurrence hayood Computer Science 1 January 31st, 2011 01:52 PM
recurrence CarpeNoctum Computer Science 3 October 12th, 2010 02:08 PM
gcd recurrence nithins Number Theory 1 April 15th, 2007 03:08 AM





Copyright © 2017 My Math Forum. All rights reserved.