My Math Forum Is there any one can help me with this recurrence ??

 Computer Science Computer Science Forum

 November 24th, 2008, 10: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
 November 24th, 2008, 11:52 AM #2 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 937 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.
November 25th, 2008, 05:52 AM   #3
Senior Member

Joined: Oct 2007
From: Chicago

Posts: 1,701
Thanks: 3

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

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

If you do that:
$T(n)=2T(n/2) + n-1\rightarrow t(k)=2t(k-1)+(2^k-1)\\
t(1)=1$

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

Doing one "iteration" gives:
$2(2t(k-2) + 2^k-1) + 2^{k-1}-1\\
4t(k-2) + 2^k + 2^{k-1} - 3$

Do you see this going anywhere?

 Tags recurrence

 Thread Tools Display Modes Linear Mode

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

 Contact - Home - Forums - Cryptocurrency Forum - Top