Can I use the Master Theorem here? (Algorithm Complexity)

AI Thread Summary
The discussion revolves around determining the complexity of the recurrence T(n) = (9/4)T((2/3)n) + n² and whether the Master Theorem can be applied. The user identifies parameters a = 9/4 and attempts to calculate b but expresses uncertainty about the value. They conclude that T(n) would be theta(n²) since it appears to exceed n^(log_b_a). The conversation also includes a note about the user's non-native English proficiency.
frank1
Messages
25
Reaction score
0

Homework Statement


What is the complexity of the following recurrence: T(n) = (9/4)T((2/3)n) + n²

Homework Equations


My question is: can I use the Master Theorem here?

The Attempt at a Solution


My attemp:
a=9/4
b=3/(1/2) (this is where I think I may be wrong)
f(n) = n²

so, in this case T(n) would be theta(n²) because it would be greater than n^(log_b_a)

Anyway, the point is if I can use Master Theorem and what would be the value of b.

PS: English is not my native english. Sorry for the grammar.
 
Physics news on Phys.org
frank1 said:

Homework Statement


What is the complexity of the following recurrence: T(n) = (9/4)T((2/3)n) + n²

Homework Equations


My question is: can I use the Master Theorem here?

The Attempt at a Solution


My attemp:
a=9/4
b=3/(1/2) (this is where I think I may be wrong)
f(n) = n²

so, in this case T(n) would be theta(n²) because it would be greater than n^(log_b_a)

Anyway, the point is if I can use Master Theorem and what would be the value of b.

PS: English is not my native english. Sorry for the grammar.
You are right. Are you in cmps101 at ucsc?
 
Back
Top