How to solve recurrences with big-O instead of big theta?

user_11091914 0
Viewed 251

I'm looking at the following problem:
T(n)=57*T(n/4) + O(n^3)
I understand that I need to use the master theorem to solve this, but all the examples in my textbook and online have big theta in the equation instead of big-O. Are the three cases the same for both? Any help is very much appreciated.

recurrence math big-o algorithm
2 Answers

Theta is good enough for your purpose:

enter image description here

user_17566360

You are right. These two are not the same:

T(n) = 57*T(n/4) + O(n^3)
T(n) = 57*T(n/4) + \Theta(n^3)

However, you can use the master theorem to reach some big-O analysis for T(n). Hence, using the second case to analyze T(n), and using O instead of Theta in the final result as if f(n) = Theta(g(n)) you can say f(n) = O(g(n)) too!

user_37688710
Related