February 25th, 2013, 12:01 PM  #1 
Newbie Joined: Feb 2013 Posts: 4 Thanks: 0  Recurrence equation
Hello I have this recurrence equation T(k) = 4T(k/3) + sqrt(k). I wonder what is growth of this function? So we have 4 recursive calls. k/3 means that k is always divided in three parts. And sqrt(k) means work. First I thought that it must be O(n log n). But no, that is wrong. I thought it over many times and came to the conclusion that growth of this function is O(n^log3 4). Do you agree with me? 
February 25th, 2013, 07:18 PM  #2 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Recurrence equation
It follows from the Master Theorem that it takes time , yes.

March 1st, 2013, 10:54 PM  #3 
Newbie Joined: Feb 2013 Posts: 4 Thanks: 0  Re: Recurrence equation
Thank you, CRGreathouse.


Tags 
equation, recurrence 
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 
Functional equation with a recurrence relation.  mathbalarka  Algebra  2  July 7th, 2012 11:43 PM 
recurrence  CarpeNoctum  Computer Science  3  October 12th, 2010 02:08 PM 
Is there any one can help me with this recurrence ??  Student 100  Computer Science  2  November 25th, 2008 05:52 AM 
gcd recurrence  nithins  Number Theory  1  April 15th, 2007 03:08 AM 