Big-O Examples - Wrean
Big-O Examples
Definition Let f and g be real-valued functions. We say that f (x) is O(g(x)) if there are constants C and k such that
|f (x)| C|g(x)| for all x > k. Example 1 Show that f (x) = 4x2 - 5x + 3 is O(x2).
|f (x)| = |4x2 - 5x + 3| |4x2| + | - 5x| + |3| 4x2 + 5x + 3, for all x > 0 4x2 + 5x2 + 3x2, for all x > 1 12x2, for all x > 1
We conclude that f (x) is O(x2). Observe that C = 12 and k = 1 from the definition of big-O.
Example 2 Show that f (x) = (x + 5) log2(3x2 + 7) is O(x log2 x). |f (x)| = |(x + 5) log2(3x2 + 7)| = (x + 5) log2(3x2 + 7), for all x > -5 (x + 5x) log2(3x2 + 7x2), for all x > 1 6x log2(10x2), for all x > 1 6x log2(x3), for all x > 10 18x log2 x, for all x > 10
We conclude that f (x) is O(x log2 x). Observe that C = 18 and k = 10 from the definition of big-O.
Example 3 Show that f (x) = (x2 + 5 log2 x)/(2x + 1) is O(x).
Since log2 x < x for all x > 0, we conclude that 5 log2 x < 5x < 5x2, for all x > 1.
Since 2x + 1 > 2x, we conclude that
1
1
< for all x > 0.
2x + 1 2x
Therefore,
|f (x)| = x2 + 5 log2 x 2x + 1
=
x2
+
5 log2
x ,
for all x > 1
2x + 1
x2 + 5x2
, for all x > 1
2x
3x, for all x > 1
We conclude that f (x) is O(x). Observe that C = 3 and k = 1 from the definition of big-O.
Gilles Cazelais. Typeset with LATEX on February 13, 2007.
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- introduction to algorithms northeastern university
- lecture 3 solving equations using fixed point iterations
- z f x dx 1 be a continuous r v f x university of california los
- convex functions university college dublin
- convex optimization — boyd vandenberghe 3 convex functions
- math 220a hw 6 solutions university of california san diego
- log normal distribution from x α β α β α william mary
- graph transformations university of utah
- chapter 1 algorithm analysis donald bren school of information and
- lecture 8 branches of multi valued functions university of washington