1  2  3  4.... 1  1  1  1  1......... ?

1  2  3  4.... Discrete mathematics

Algorithms
x y( x  y )

x(  | x )
 1 Chapter 3

x 1
x
?

 x 1
x ?
RIZOAN TOUFIQ
ASSISTANT PROFESSOR
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJSHAHI UNIVERSITY OF ENGINEERING & TECHNOLOGY
The Growth of Functions

Section 3.2
 Section Summary

 Big-O Notation
 Big-O Estimates for Important Functions
 Big-Omega and Big-Theta Notation
Donald E. Knuth
(Born 1938)

Edmund Landau Paul Gustav Heinrich

(1877-1938) Bachmann
(1837-1920)
 The Growth of Functions

 In both computer science and in mathematics, there are

many times when we care about how fast a function grows.
 In computer science, we want to understand how quickly an
algorithm can solve a problem as the size of the input grows.
– We can compare the efficiency of two different algorithms for
solving the same problem.
– We can also determine whether it is practical to use a particular
algorithm as the input grows.
– We’ll study these questions in Section 3.3.
 Two of the areas of mathematics where questions about the
growth of functions are studied are:
– number theory (covered in Chapter 4)
– combinatorics (covered in Chapters 6 and 8)
 Big-O Notation

Definition: Let f and g be functions from the set of

integers or the set of real numbers to the set of real
numbers. We say that f(x) is O(g(x)) if there are
constants C and k such that

whenever x > k. (illustration on next slide)

 This is read as “f(x) is big-O of g(x)” or “g
asymptotically dominates f.”
 The constants C and k are called witnesses to the
relationship f(x) is O(g(x)). Only one pair of witnesses is
needed.
Illustration of Big-O Notation

f(x) is O(g(x)
 Some Important Points about
Big-O Notation
 If one pair of witnesses is found, then there are infinitely
many pairs. We can always make the k or the C larger and
still maintain the inequality .
– Any pair C ̍ and k̍ where C < C̍ and k < k ̍ is also a pair of witnesses
since whenever x > k̍ > k.
You may see “ f(x) = O(g(x))” instead of “ f(x) is O(g(x)).”
– But this is an abuse of the equals sign since the meaning is that
there is an inequality relating the values of f and g, for sufficiently
large values of x.
– It is ok to write f(x) ∊ O(g(x)), because O(g(x)) represents the set of
functions that are O(g(x)).
 Usually, we will drop the absolute value sign since we will
always deal with functions that take on positive values.
 Using the Definition of Big-O
Notation
Example: Show that is .
Solution: Since when x > 1, x < x2 and 1 < x2

– Can take C = 4 and k = 1 as witnesses to show that

(see graph on next slide)
 Alternatively, when x > 2, we have 2x ≤ x2 and 1 < x2.
Hence,
when x > 2.
– Can take C = 3 and k = 2 as witnesses instead.
Illustration of Big-O Notation

is
 Big-O Notation

 Both and
are such that and .
We say that the two functions are of the same order. (More on this
later)

 If and h(x) is larger than g(x) for all positive

real numbers, then .

 Note that if for x > k and if

for all x, then if x > k. Hence, .

 For many applications, the goal is to select the function g(x) in

O(g(x)) as small as possible (up to multiplication by a constant, of
course).
 Using the Definition of Big-O
Notation
Example: Show that 7x2 is O(x3).
Solution: When x > 7, 7x2 < x3. Take C =1 and k = 7 as
witnesses to establish that 7x2 is O(x3).
(Would C = 7 and k = 1 work?)
Example: Show that n2 is not O(n).
Solution: Suppose there are constants C and k for which
n2 ≤ Cn, whenever n > k. Then (by dividing both sides
of n2 ≤ Cn) by n, then n ≤ C must hold for all n > k. A
contradiction!
 Big-O Estimates for
Polynomials
Example: Let
where are real numbers with an ≠0.
Then f(x) is O(xn). Uses triangle inequality, an
Proof: |f(x)| = |anxn + an-1 xn-1 + ∙∙∙ + a1x1 + a0| exercise in Section 1.8.
≤ |an|xn + |an-1| xn-1 + ∙∙∙ + |a1|x1 + |a0|
= xn (|an| + |an-1| /x + ∙∙∙ + |a1|/xn-1 + |a0|/ xn)
Assuming x > 1 ≤ xn (|an| + |an-1| + ∙∙∙ + |a1|+ |a0|)
 Take C = |an| + |an-1| + ∙∙∙ + |a0| and k = 1. Then f(x) is
O(xn).
 The leading term anxn of a polynomial dominates its growth.
 Big-O Estimates for some
Important Functions
Example: Use big-O notation to estimate the sum of the
first n positive integers.
Solution:

Example: Use big-O notation to estimate the factorial

function
Solution:

Continued →
 Big-O Estimates for some
Important Functions
Example: Use big-O notation to estimate log n!
Solution: Given that (previous slide)
then .
Hence, log(n!) is O(n∙log(n)) taking C = 1 and k = 1.
Display of Growth of Functions

Note the difference in behavior of functions as n

gets larger
 Useful Big-O Estimates Involving
Logarithms, Powers, and Exponents

 If d > c > 1, then

nc is O(nd), but nd is not O(nc).
 If b > 1 and c and d are positive, then
(logb n)c is O(nd), but nd is not O((logb n)c).
 If b > 1 and d is positive, then
nd is O(bn), but bn is not O(nd).
 If c > b > 1, then
bn is O(cn), but cn is not O(bn).
 Combinations of Functions

 If f1 (x) is O(g1(x)) and f2 (x) is O(g2(x)) then

( f1 + f2 )(x) is O(max(|g1(x) |,|g2(x) |)).

– See next slide for proof

 If f1 (x) and f2 (x) are both O(g(x)) then

( f1 + f2 )(x) is O(g(x)).
– See text for argument
 If f1 (x) is O(g1(x)) and f2 (x) is O(g2(x)) then
( f1 f2 )(x) is O(g1(x)g2(x)).
– See text for argument
 Combinations of Functions

 If f1 (x) is O(g1(x)) and f2 (x) is O(g2(x)) then

( f1 + f2 )(x) is O(max(|g1(x) |,|g2(x) |)).

– By the definition of big-O notation, there are constants C1,C2 ,k1,k2 such that
| f1 (x) ≤ C1|g1(x) | when x > k1 and f2 (x) ≤ C2|g2(x) | when x > k2 .
– |( f1 + f2 )(x)| = |f1(x) + f2(x)|
≤ |f1 (x)| + |f2 (x)| by the triangle inequality |a + b| ≤ |a| + |b|
– |f1 (x)| + |f2 (x)| ≤ C1|g1(x) | + C2|g2(x) |
≤ C1|g(x) | + C2|g(x) | where g(x) = max(|g1(x)|,|g2(x)|)
= (C1 + C2) |g(x)|
= C|g(x)| where C = C1 + C2
– Therefore |( f1 + f2 )(x)| ≤ C|g(x)| whenever x > k, where k = max(k1,k2).
 Ordering Functions by Order
of Growth
 Put the functions below in order so that each function is big-
O of the next function on the list.
 f1(n) = (1.5)n
 f2(n) = 8n3+17n2 +111
 f3(n) = (log n )2 We solve this exercise by successively finding the function that grows
slowest among all those left on the list.
 f4 (n ) = 2n
• f (n) = 10000 (constant, does not increase with n)
 f5(n) = log (log n) 9

 f6(n) = n2 (log n)3 •f (n) = log (log n) (grows slowest of all the others)
5

 f7(n) = 2n (n2 +1) •f (n) = (log n ) 2

(grows next slowest)
3

 f8(n) = n3+ n(log n)2 •f (n) = n (log n) (next largest, (log n) factor smaller than any power of n)
6
2 3 3

 f9(n) = 10000 •f (n) = 8n +17n +111 (tied with the one below)
3 2
2

 f10(n) = n! •f (n) = n + n(log n) 3 2

(tied with the one above)
8

•f1(n) = (1.5)n (next largest, an exponential function)

•f4(n) = 2n (grows faster than one above since 2 > 1.5)

•f7(n) = 2n (n2 +1) (grows faster than above because of the n2 +1 factor)

•f10(n) = n! ( n! grows faster than cn for every c)

 Big-Omega Notation

Definition: Let f and g be functions from the set of

integers or the set of real numbers to the set of real
numbers. We say that Ω is the upper
if there are constants C and k such that case version of
when x > k. the lower case
 We say that “f(x) is big-Omega of g(x).” Greek letter ω.
 Big-O gives an upper bound on the growth of a function,
while Big-Omega gives a lower bound. Big-Omega tells
us that a function grows at least as fast as another.
 f(x) is Ω(g(x)) if and only if g(x) is O(f(x)). This follows
from the definitions. See the text for details.
 Big-Omega Notation

Example: Show that is

where .
Solution: for all
positive real numbers x.
– Is it also the case that is ?
 Big-Theta Notation

 Definition: Let f and g be functions from the set of

integers or the set of real numbers to the set of real
numbers. The function if
and .

 We say that “f is big-Theta of g(x)” and also that “f(x) is

of order g(x)” and also that “f(x) and g(x) are of the
same order.”
 if and only if there exists constants C1
, C2 and k such that C1g(x) < f(x) < C2 g(x) if x > k. This
follows from the definitions of big-O and big-Omega.

Θ is the upper case version of

the lower case Greek letter θ.
 Big Theta Notation

Example: Show that the sum of the first n positive integers is

Θ(n2).
Solution: Let f(n) = 1 + 2 + ∙∙∙ + n.
– We have already shown that f(n) is O(n2).
– To show that f(n) is Ω(n2), we need a positive constant C such that
f(n) > Cn2 for sufficiently large n. Summing only the terms greater than
n/2 we obtain the inequality
1 + 2 + ∙∙∙ + n ≥ ⌈ n/2⌉ + (⌈ n/2⌉ + 1) + ∙∙∙ + n
≥ ⌈ n/2⌉ + ⌈ n/2⌉ + ∙∙∙ + ⌈ n/2⌉
= (n − ⌈ n/2⌉ + 1 ) ⌈ n/2⌉
≥ (n/2)(n/2) = n2/4
– Taking C = ¼, f(n) > Cn2 for all positive integers n. Hence, f(n) is
Ω(n2), and we can conclude that f(n) is Θ(n2).
 Big-Theta Notation

Example: Sh0w that f(x) = 3x2 + 8x log x is Θ(x2).

Solution:
• 3x2 + 8x log x ≤ 11x2 for x > 1,
since 0 ≤ 8x log x ≤ 8x2 .
– Hence, 3x2 + 8x log x is O(x2).
• x2 is clearly O(3x2 + 8x log x)
• Hence, 3x2 + 8x log x is Θ(x2).
 Big-Theta Notation

 When it must also be the case that

 Note that if and only if it is the case

that and .
 Sometimes writers are careless and write as if big-O
notation has the same meaning as big-Theta.
 Big-Theta Estimates for
Polynomials
Theorem: Let
where are real numbers with an ≠0.
Then f(x) is of order xn (or Θ(xn)).
(The proof is an exercise.)
Example:
The polynomial is order of x5 (or
Θ(x5)).
The polynomial
is order of x199 (or Θ(x199) ).
 Query???

1  2  3  4.... x y( x  y )  ?


 x 1 x  ?  1
 x 1
x
?

x(  | x )  ? x y( x  y )  ?

 1
1  2  3  4....  ?
1  1  1  1  1......... ?
 x 1
x
?