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
- homework 1 solutions ucla mathematics
- converting exponential equations to logarithmic equations
- 1 1 e log2 p d log p log q 2x log x o x v x z d log2 x d
- solving log equations part 1
- logarithms tutorial for chemistry students 1 logarithms boston university
- worksheet logarithmic function department of mathematics
- big o examples wrean
- problem set week 3 class 2 solutions icgn104 mathematics and its
- solving equations using logs
- maths genie free online gcse and a level maths revision