
Computer Science Computer Science Forum 
 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) + (n1) n>2 ; Hint :" Merge Sort " please help me with anything 
November 24th, 2008, 12:52 PM  #2 
Global Moderator 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.

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:
If you do that: where t(k) = T(2^k) [=T(n)]. Doing one "iteration" gives: Do you see this going anywhere?  

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 