JPHamlett
2015-04-02 20:53:25
Can someone go over proving if a function is Big O of another function and omega?
SRL Archive - Mathematics
Growth of Functions
J_R
2015-04-05 07:22:42
I guess one way to 'prove' a function f is Big O of another function g is to take lim(f/g) as n->infinity. If f = O(g) then this limit will come out to a constant. Also if this constant is 0, it also means f is in O(g) by definition since big O is meant to be *a* upper bound on the growth of a function.
To prove omega, you should probably go about it with showing that if f is Omega(g) then f >= g for all n bigger than a certain N (sometimes it works for all n). Another way to check Omega is actually by the same method I gave in finding big O. However you want this limit to not be 0 this time as Omega is meant to be *a* lower bound on the growth of your function.
To prove omega, you should probably go about it with showing that if f is Omega(g) then f >= g for all n bigger than a certain N (sometimes it works for all n). Another way to check Omega is actually by the same method I gave in finding big O. However you want this limit to not be 0 this time as Omega is meant to be *a* lower bound on the growth of your function.