Can someone go over proving if a function is Big O of another function and omega?
Can someone go over proving if a function is Big O of another function and omega?
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.
In order to do this you will need to use the definition and find both a c and a n0 s.t. 0<=f(n)<=cg(n) and n>n0
That will prove f(n) is upper bounded by g(n) and that f(n) = O(g(n)).
Omega is similar but you will need to use the definition for Omega and find c and n0 s.t. 0<=cg(n)<=f(n) and n>n0
... I thought maybe someone would appreciate correctness on this website
I'm also really bad at math and can't even slove first order equation. I'm actively looking for different programs, which provides an expert homework help.
I can recommend you a writingcheap.com, very good assignment writing service.
In my opinion, if you can't keep up with math and other subjects, just ask professionals for help.
There are currently 1 users browsing this thread. (0 members and 1 guests)