Can I use Master Theorem if the partitions are not fractions?

Click For Summary

Discussion Overview

The discussion revolves around the application of the Master Theorem to a recurrence relation that involves partitions of size n - 1, specifically questioning how to determine the "b" value in this context. The scope includes theoretical considerations of recurrence relations and methods for solving them.

Discussion Character

  • Homework-related
  • Technical explanation
  • Exploratory

Main Points Raised

  • One participant questions how to apply the Master Theorem to a recurrence of the form 2 C(n-1) + f(n) and expresses uncertainty about the "b" value.
  • Another participant suggests that the Master Theorem cannot be applied in this case and recommends using the recursion tree method, asserting that the growth will be exponential due to the doubling of nodes at each level.
  • A participant expresses confusion about the recursion tree method and notes that while the number of calls doubles, they are also on one less element, questioning the implications of this.
  • A later reply speculates that if a closed form expression is found, it might be 2^n, but acknowledges that this depends on the initial condition C(0) and the function f(n).
  • There is a mention that f(n) is constant, but the value of C(0) remains unspecified.

Areas of Agreement / Disagreement

Participants do not reach a consensus on the applicability of the Master Theorem, with some asserting it cannot be used while others explore the implications of the recursion tree method. The discussion remains unresolved regarding the specifics of the recurrence relation and its solution.

Contextual Notes

The discussion highlights limitations in the understanding of the recursion tree method and the implications of the initial condition C(0) and the function f(n) on the closed form expression.

zeion
Messages
455
Reaction score
1

Homework Statement



If I had a recurrence expression that recurs on partitions of size n - 1 each time, (as opposed some fraction of the original size ie. n/2), how can I apply the Master Theorem? I don't know what the "b" value is?


Homework Equations





The Attempt at a Solution



ie. If I had 2 C(n-1) + f(n), what is b?
 
Physics news on Phys.org
You can not use the Master Theorem in this case, just use the recursion tree method. In this case it is easy to see that it will be exponential, since each level has twice the number of nodes of the previous level.
 
Max.Planck said:
You can not use the Master Theorem in this case, just use the recursion tree method. In this case it is easy to see that it will be exponential, since each level has twice the number of nodes of the previous level.

I'm not sure what a recursion tree method is..
I see that each recursion will have twice the calls to the function as the last, but they are also on one less element than the last, does that matter?

Actually nevermind, so if I find a closed form expression it will be 2^n, right?
 
zeion said:
Actually nevermind, so if I find a closed form expression it will be 2^n, right?

Depends on C(0) and f(n). The recursion tree method should be described in your textbook.
 
Oh I see. It says that f(n) is constant. But it doesn't say what C(0) is.
 

Similar threads

Can I use the Master Theorem here? (Algorithm Complexity)
  • · Replies 1 ·
Replies
1
Views
2K
Final project ideas using Noether's theorem in simulation class
  • · Replies 4 ·
Replies
4
Views
2K
High School Some questions to understand Riemann integrability criterion
  • · Replies 12 ·
Replies
12
Views
3K
MHB Master Theorem-Relation of the two functions
  • · Replies 2 ·
Replies
2
Views
1K
Partition Coefficient and Retardation Factor
  • · Replies 1 ·
Replies
1
Views
3K
Proof of optimality of algorithm
  • · Replies 9 ·
Replies
9
Views
2K
Converting .11111 to binary w/o converting to fraction
  • · Replies 10 ·
Replies
10
Views
5K
Canonical partition function for two coupled oscillators
  • · Replies 1 ·
Replies
1
Views
2K
What are some less famous equations that you must know as an undergraduate physicist?
  • · Replies 21 ·
Replies
21
Views
5K
MHB Solving Recurrence Relations Using Master Theorem/Akra-Bazzi
  • · Replies 1 ·
Replies
1
Views
2K