My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum

LinkBack Thread Tools Display Modes
February 25th, 2013, 12:01 PM   #1
Joined: Feb 2013

Posts: 4
Thanks: 0

Recurrence equation


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?
Oscarmovies is offline  
February 25th, 2013, 07:18 PM   #2
Global Moderator
CRGreathouse's Avatar
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.
CRGreathouse is offline  
March 1st, 2013, 10:54 PM   #3
Joined: Feb 2013

Posts: 4
Thanks: 0

Re: Recurrence equation

Thank you, CRGreathouse.
Oscarmovies is offline  

  My Math Forum > Science Forums > Computer Science

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

Copyright © 2019 My Math Forum. All rights reserved.