Thread: Growth of Functions

1. Growth of Functions

Can someone go over proving if a function is Big O of another function and omega?

2. J_R
SRL Member
Join Date
May 2014
Posts
633
Mentioned
8 Post(s)
Quoted
322 Post(s)
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.

3. Registered User
Join Date
Feb 2018
Posts
12
Mentioned
0 Post(s)
Quoted
4 Post(s)
Originally Posted by JPHamlett
Can someone go over proving if a function is Big O of another function and omega?
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

4. Registered User
Join Date
Feb 2018
Posts
12
Mentioned
0 Post(s)
Quoted
4 Post(s)
Originally Posted by J_R
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.
you may need to know L'hopitals rule for that. Just a heads up to the op

5. Originally Posted by hunterofagoodtime
you may need to know L'hopitals rule for that. Just a heads up to the op
I'm sure he is still struggling after almost 3 years.

6. Originally Posted by Citrus
I'm sure he is still struggling after almost 3 years.
lolol

7. SRL Member
Join Date
Nov 2006
Posts
1,103
Mentioned
0 Post(s)
Quoted
6 Post(s)
Originally Posted by Citrus
I'm sure he is still struggling after almost 3 years.
It's called a PhD....

8. Registered User
Join Date
Feb 2018
Posts
12
Mentioned
0 Post(s)
Quoted
4 Post(s)
... I thought maybe someone would appreciate correctness on this website

9. Registered User
Join Date
May 2018
Location
Posts
6
Mentioned
0 Post(s)
Quoted
0 Post(s)
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.