Alright, I see. If we can prove that there is a value n for which f(n) < 0(n^4). Then it is true.Look at the post I made in the other thread. Just find a value of c and N for which the required relationship holds.
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).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.
That makes sense. Thank you so much for your help.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.
Either Java or C++. Though mostly C++.On a slightly seperate note, what is the program you are using here to write in?
Sorry, I misunderstood. I'm using an app called GoodNotes. I have an iPad Pro and an apple pencil so it's a perfect combination.On a slightly seperate note, what is the program you are using here to write in?
Thank you!Sorry, I misunderstood. I'm using an app called GoodNotes. I have an iPad Pro and an apple pencil so it's a perfect combination.
Thread starter | Similar threads | Forum | Replies | Date |
---|---|---|---|---|
Y | proving radiation orthogonality between two antennas | Wireless & RF Design | 0 | |
Y | proving delta | Wireless & RF Design | 1 | |
Proving the tolerance of a 0Ω resistor | General Electronics Chat | 29 | ||
Z | Proving a^ib^ja^(i.j) | i, j > =0; using Pumping Lemma | Homework Help | 4 | |
Help with proving a transfer function? | Homework Help | 1 |
by Jake Hertz
by Jake Hertz
by Jake Hertz