Message Boards Message Boards

0
|
2592 Views
|
4 Replies
|
2 Total Likes
View groups...
Share
Share this post:

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

Posted 7 years ago

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!

POSTED BY: Cael G
4 Replies

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 *)
POSTED BY: Daniel Lichtblau

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?

POSTED BY: Gianluca Gorni

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]]
POSTED BY: Gianluca Gorni
Posted 7 years ago

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.

POSTED BY: Cael G
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract