big O notation help

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

Answer 1

[Walter Roberson]

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.

[Walter Roberson]

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]

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]

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]

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]

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]

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]

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]

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]

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]

Yes, all answers have to be done using Matlab

Answer 2

[Walter Roberson]

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.

[Harry]

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]

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]

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]

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]

I can also do it for question 2 but its too expensive and inaccurate to be considered even partially useful.