big O notation help

2012 1 20
2 个回答
4 次查看（30 天）

0 个投票

I'm trying to write a function f in the form f(h) = O(h^p) with the largest possible integer p:
f(h) = 10(h^2+h)^2 - 10h^4
By pen and paper I get it to be O(h^3) because the h^4 terms cancel. I have tried a few different ways of calculating it using Matlab but I keep running into problems and I wondered if anyone could give me any pointers as to the best way of approaching the problem?
The most recent attempt is
function p = bigOh(f)
for i = 1:500 syms h
lim = limit(f/h^i,Inf);
lim = double(lim);
fprintf(1,'limit = %f\n',lim);
TF = isfinite(lim);
if TF == 1
p = i;
fprintf(1, 'f(h) = O(h^%d)',p);
break
end
end
However, this gives me an error when it gets to the correct value of i.
i.e. if f = h^4, then when i = 4 I get the following error messages:
??? Error using ==> map>checkstat at 29 Error: invalid limit variable (expecting an identifier) [checkpointt]
Error in ==> map at 15 checkstat(result,status,nargout);
Error in ==> sym.limit at 70 r = map(f,'mllimit',dirpt{:});
Error in ==> bigOh at 5 lim = limit(f/h^i,Inf);
Thanks in advance

请先登录，再回答此问题。

回答（2 个）

Walter Roberson
Walter Roberson 2012-1-20

0 个投票

double() can convert a symbolic number to double precision.
You could also compare abs(lim) to sym(inf)
However, limit(f) to infinity is going to be infinity unless f is constant.
Your calculation does not use "i" in the loop, so you are just repeating the same calculation over and over again.
I do know the solution, but as the small number of lines would handle the entire assignment, I can't really say anything other than the approach you are following is not going to be productive.

10 个评论
显示 8更早的评论 隐藏 8更早的评论

Walter Roberson
Walter Roberson 2012-1-20
Hmmm, that might be okay.
Is f certain to be a polynomial? And as you are using the limit() function which is part of the symbolic toolkit, is f certain to be symbolic?
Harry
Harry 2012-1-20
No the second f I need to evaluate is an exponential. Which I don't understand as surely it can't be put into the form O(h^p)
Harry
Harry 2012-1-20
I can tell you that there are four f's I need to evaluate. The one that I have already told you and the following three:
2. ((e^h-e^-h)/2h) - 1
3. g'(x) - (g(x+h) - g(x-h))/2h
4. g'(x) - g(x+h_1)-g(x-h_2)/(h_1 +h_2)
Walter Roberson
Walter Roberson 2012-1-20
The purpose of including the exponential (if it is a positive exponential) could be as simple as illustrating that exponential grows faster than any polynomial.
Harry
Harry 2012-1-20
I've not even got a clue with the last two yet, so I'm just focusing on the first one to begin with. It seems to me that there does not exist a value of p for 2.
Harry
Harry 2012-1-20
But then if I ran the second one through a for loop from 1 to 500 this seems like an expensive way to then just say that it can't be done. And an inaccurate one.
Walter Roberson
Walter Roberson 2012-1-20
I am not sure that the last two can be done without knowing something about g(x).
On the other hand #3 reminds me of a theorem from first year calculus (mumble) many years ago, at least as h approaches 0, and #4 looks like the slight generalization of that theorem to the case where the probe points are not centered around g(x). #4 cannot be handled in terms of the order of h (other than as a constant), as it does not involve h at all unless g(x) involves h.
It is not hard to show that #2 goes to exp(h)/h as h increases even moderately, which takes us back to the "It might just be to prove a point" hypothesis.
Harry
Harry 2012-1-20
I know that g is in C^Inf(R) and I recognise that the formula is a version of the test for differentiability when h->0. But without being able to do this for a polynomial I can't see my self doing it for 3 or 4
Walter Roberson
Walter Roberson 2012-1-20
Are you required to prove the results mechanically?
Interestingly, Maple knows the relationship:
> limit((D(g))(x)-(1/2)*(g(x+h)-g(x-h))/h, h=0)
0
But that's for h approaching 0, not for h approaching infinity.
Harry
Harry 2012-1-20
Yes, all answers have to be done using Matlab

请先登录，再进行评论。

Walter Roberson
Walter Roberson 2012-1-20

0 个投票

When your f is exactly h^n then you would be asking for the limit of h^n / h^i which is h^(n-i) . Now when i exactly equal to n, that would be h^0 which is 1, which is a constant that has no identifier in it, and limit() would not be able to find an identifier to take the limit against.

5 个评论
显示 3更早的评论 隐藏 3更早的评论

Harry
Harry 2012-1-20
Right I see... so it won't just evaluate the limit to be 1. Which puts a spanner in the works. So in that case is there a matlab function that I could use to check whether h^n/h^i isconstant? I've googled it and there doesn't seem to be.
Thank you so much for your help by the way.
Walter Roberson
Walter Roberson 2012-1-20
There are MuPAD functions that can test that explicitly. Or you can do a quick and dirty test by checking to see if symvar() of the expression is empty.
Walter Roberson
Walter Roberson 2012-1-20
Also, if you had explicitly provided the variable name to take the limit over, possibly it would not be looking for variable names. No promises on that, though; I do not have MuPAD to test that with.
Harry
Harry 2012-1-20
I have now done it for any polynomial using the symvar method. I'm now trying to work out how to do the other questions.
Harry
Harry 2012-1-20
I can also do it for question 2 but its too expensive and inaccurate to be considered even partially useful.

请先登录，再进行评论。

类别

在 帮助中心 和 File Exchange 中查找有关 Utilities for the Solver 的更多信息

标签

提问:

Harry
Harry
2012-1-20

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by