[?] Find the constant (C) when determining big-O of a function?

Questions
1

Hi,
I’m new to Mathematica and recently started to explore on algorithm complexity. Using an example,

Show that f (x) = x² + 2x + 1 is O(x²)

I want to use Mathematica to calculate the constant of the C such that f(x)<=C.g(x) whenever x>k.

Manually, C can be calculated by replacing the degree/power from the leading coefficients to all the coefficients per examples below

Example 1:

C = x² + 2x + 1

= x² + 2x² + x²

= 4x²

Example 2:

C = 6x + 11

= 6x + x

= 7x

Therefore, is there any function that could be used in Mathematica that could help me calculate C from a function? I tried Coefficient and CoefficientList but it doesn’t do what I want. Thanks!

2

I would use MaxValue:

MaxValue[{Abs[(x^2 + 2 x + 1)/x^2], Abs[x] >= 1}, x]

If you insist on using the rule of replacing powers, here is a way using CoefficientList and Total:

f[x_] = x^2 + 2 x + 1;
Total[CoefficientList[f[x], x] x^Exponent[f[x], x]]
3

Thanks for the reply. I tried the function using CoefficientList and Total on this example 2 with the last coefficient larger than 1:

f[x_] = 6x + 11;
Total[CoefficientList[f[x], x] x^Exponent[f[x], x]]

However, the output produced is 17x instead of 7x due to the calculation of the last coefficient (it should convert the last coefficient [11] → x). Is there a way to achieve this?

Edit: Found a way which kinda works:

Total[CoefficientList[f[x], x]] - (Coefficient[f[x], x, 0] - 1)

but will like to know if there’s a more efficient way than this.

4

I don’t understand why you may want that, but here is a way:

f[x_] = 6 x + 11;
Total[CoefficientList[f[x] - f[0], x] x^Exponent[f[x], x]]

What do you expect to find when there the coefficients are not all positive, like in f[x]=x^2-x?

5

If you know or at least suspect if is O(x^2) you can do an asymptotic series expansion of the function divided by that.

asympExpansion = Series[(x^2 + 2 x + 1)/x^2, {x, Infinity, 0}]

(* Out[271]= SeriesData[x, DirectedInfinity[1], {1}, 0, 1, 1] *)

Normal[asympExpansion]

(* Out[273]= 1 *)