Group Abstract Group Abstract

Message Boards Message Boards

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

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

Cael G
Posted 8 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
Sort By:

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

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
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Tag limit exceeded
Note: Only the first five people you tag will receive an email notification; the other tagged names will appear as links to their profiles.
Reply Preview
Attachments
Remove
or Discard