My Math Forum Recurrence equation

 Computer Science Computer Science Forum

 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 $\Theta(n^{\log_34})$, 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 Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post One Real Analysis 2 June 17th, 2013 01:20 PM mathbalarka Algebra 2 July 7th, 2012 11:43 PM CarpeNoctum Computer Science 3 October 12th, 2010 02:08 PM Student 100 Computer Science 2 November 25th, 2008 05:52 AM nithins Number Theory 1 April 15th, 2007 03:08 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top