Proving that a function is equal to a big O function

Thread Starter

asilvester635

Joined Jan 26, 2017
73
Can someone give me a hint to get me started? Below is the problem. It's proving that a function is equal to a big O function.

20170207_184155000_iOS.jpg
 
Last edited by a moderator:

WBahn

Joined Mar 31, 2012
29,976
Look at the post I made in the other thread. Just find a value of c and N for which the required relationship holds.
 

WBahn

Joined Mar 31, 2012
29,976
The required relationship says nothing about

f(n) ≤ n^4 for all n greater than N,

is says that there exists a positive constant c and a value N such that

f(n) ≤ c · n^4 for all n greater than N.

Also, n is the size of a problem. It is meaningless to talk about negative problem sizes, so f(n) is only defined for n ≥ 0.
 

Thread Starter

asilvester635

Joined Jan 26, 2017
73
The required relationship says nothing about

f(n) ≤ n^4 for all n greater than N,

is says that there exists a positive constant c and a value N such that

f(n) ≤ c · n^4 for all n greater than N.

Also, n is the size of a problem. It is meaningless to talk about negative problem sizes, so f(n) is only defined for n ≥ 0.
Okay, I'm getting the hang of these problems. Is there a way to find the exact constant c? I can find a constant 'c' through trial and error in my calculator. I plug in and multiply g(n) by numbers > 0, increasing in increment by 1, and I look at the graph and its output from the calculator. I found that when c >= 5, f(n) <= c * n^4. For n I found that when n >= 3, f(n) <= c * n^4. Therefore we have proved that f(n) is O(n^4).
 

WBahn

Joined Mar 31, 2012
29,976
In general the value of c and the value of N are linked. But all that matters is that they exist, we don't have to actually find them. But finding the relationship is pretty easy.

\(
4n^4 \; + \; 5n^2 \; + \; 32 \; \leq \; cn^4
\)

Solve for c.

\(
c \; \geq \; 4 \; + \; \frac{5}{n^2} \; + \; \frac{32}{n^4}
\)

So pick a value of n = no and this will tell you the minimum value of c that will work for that value of no. If we want it to work for every value of n including n=1, the all we have to do is pick c=41 (or higher). Notice that we cannot pick c=4 because there is no finite value of no for which this relation will hold. But we CAN pick 4+ε where ε can be arbitrarily small.
 
Last edited:

Thread Starter

asilvester635

Joined Jan 26, 2017
73
In general the value of c and the value of N are linked. But all that matters is that they exist, we don't have to actually find them. But finding the relationship is pretty easy.

\(
4n^4 \; + \; 5n^2 \; + \; 32 \; \leq \; cn^4
\)

Solve for c.

\(
c \; \geq \; 4 \; + \; \frac{5}{n^2} \; + \; \frac{32}{n^4}
\)

So pick a value of n = no and this will tell you the minimum value of c that will work for that value of no. If we want it to work for every value of n including n=1, the all we have to do is pick c=41 (or higher). Notice that we cannot pick c=4 because there is no finite value of no for which this relation will hold. But we CAN pick 4+ε where ε can be arbitrarily small.
That makes sense. Thank you so much for your help.
 
Top