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

Join the discussion
Ask a follow-up here, or get your own question answered by working scientists, mathematicians and engineers — people, not an autocomplete.
Real named experts · corrections over time · the nuance an AI answer skips
1 reply · 2K views
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?