ASYMTOTIC NOTATION ON DATA STRUCTURE AND ALGORITHM

ASYMTOTIC NOTATIONS

1. August 3, 2024 Comp 122, Spring 2004
Asymptotic Notation,
Review of Functions &
Summations

2. Comp 122asymp - 2
Asymptotic Complexity
Running time of an algorithm as a function of
input size n for large n.
Expressed using only the highest-order term in
the expression for the exact running time.
Instead of exact running time, say (n
2
).
Describes behavior of function in the limit.
Written using Asymptotic Notation.

3. Comp 122asymp - 3
Asymptotic Notation
 , O, , o, 
Defined for functions over the natural numbers.
Ex: f(n) = (n
2
).
Describes how f(n) grows in comparison to n
2
.
Define a set of functions; in practice used to compare
two function sizes.
The notations describe different rate-of-growth
relations between the defining function and the
defined set of functions.

4. Comp 122asymp - 4
-notation
(g(n)) = {f(n) :
 positive constants c
1
, c
2
, and n
0,

such that n  n
0
,
we have 0  c
1g(n)  f(n) 
c
2g(n)
}
For function g(n), we define (g(n)),
big-Theta of n, as the set:
g(n) is an asymptotically tight bound for f(n).
Intuitively: Set of all functions that
have the same rate of growth as g(n).

5. Comp 122asymp - 5
-notation
(g(n)) = {f(n) :
 positive constants c
1
, c
2
, and n
0,

such that n  n
0
,
we have 0  c
1g(n)  f(n) 
c
2g(n)
}
For function g(n), we define (g(n)),
big-Theta of n, as the set:
Technically, f(n)  (g(n)).
Older usage, f(n) = (g(n)).
I’ll accept either…
f(n) and g(n) are nonnegative, for large n.

6. Comp 122asymp - 6
Example
10n
2
- 3n = (n
2
)
What constants for n
0, c
1, and c
2 will work?
Make c
1 a little smaller than the leading
coefficient, and c
2 a little bigger.
To compare orders of growth, look at the
leading term.
Exercise: Prove that n
2
/2-3n= (n
2
)
(g(n)) = {f(n) :  positive constants c
1, c
2, and n
0,
such that n  n
0, 0  c
1g(n)  f(n)  c
2g(n)}

7. Comp 122asymp - 7
Example
Is 3n
3
 (n
4
) ??
How about 2
2n
 (2
n
)??
(g(n)) = {f(n) :  positive constants c
1, c
2, and n
0,
such that n  n
0, 0  c
1g(n)  f(n)  c
2g(n)}

8. Comp 122asymp - 8
O-notation
O(g(n)) = {f(n) :
 positive constants c and n
0,

such that n  n
0
,
we have 0  f(n)  cg(n) }
For function g(n), we define O(g(n)),
big-O of n, as the set:
g(n) is an asymptotic upper bound for f(n).
Intuitively: Set of all functions
whose rate of growth is the same as
or lower than that of g(n).
f(n) = (g(n))  f(n) = O(g(n)).
(g(n))  O(g(n)).

9. Comp 122asymp - 9
Examples
Any linear function an + b is in O(n
2
). How?
Show that 3n
3
=O(n
4
) for appropriate c and n
0.
O(g(n)) = {f(n) :  positive constants c and n
0,
such that n  n
0, we have 0  f(n)  cg(n) }

10. Comp 122asymp - 10
 -notation
g(n) is an asymptotic lower bound for f(n).
Intuitively: Set of all functions
whose rate of growth is the same
as or higher than that of g(n).
f(n) = (g(n))  f(n) = (g(n)).
(g(n))  (g(n)).
(g(n)) = {f(n) :
 positive constants c and n
0,

such that n  n
0
,
we have 0  cg(n)  f(n)}
For function g(n), we define (g(n)),
big-Omega of n, as the set:

11. Comp 122asymp - 11
Example
n = (lg n). Choose c and n
0.
(g(n)) = {f(n) :  positive constants c and n
0, such
that n  n
0, we have 0  cg(n)  f(n)}

12. Comp 122asymp - 12
Relations Between , O, 

13. Comp 122asymp - 13
Relations Between , , O
I.e., (g(n)) = O(g(n))  (g(n))
In practice, asymptotically tight bounds are
obtained from asymptotic upper and lower bounds.
Theorem : For any two functions g(n) and f(n),
f(n) = (g(n)) iff
f(n) = O(g(n)) and f(n) = (g(n)).

14. Comp 122asymp - 14
Running Times
“Running time is O(f(n))”  Worst case is O(f(n))
O(f(n)) bound on the worst-case running time 
O(f(n)) bound on the running time of every input.
(f(n)) bound on the worst-case running time 
(f(n)) bound on the running time of every input.
“Running time is (f(n))”  Best case is (f(n))
Can still say “Worst-case running time is (f(n))”
Means worst-case running time is given by some
unspecified function g(n)  (f(n)).

15. Comp 122asymp - 15
Example
Insertion sort takes (n
2
) in the worst case, so
sorting (as a problem) is O(n
2
). Why?
Any sort algorithm must look at each item, so
sorting is (n).
In fact, using (e.g.) merge sort, sorting is (n lg n)
in the worst case.
Later, we will prove that we cannot hope that any
comparison sort to do better in the worst case.

16. Comp 122asymp - 16
Asymptotic Notation in Equations
Can use asymptotic notation in equations to
replace expressions containing lower-order terms.
For example,
4n
3
+ 3n
2
+ 2n + 1 = 4n
3
+ 3n
2
+ (n)
= 4n
3
+ (n
2
) = (n
3
). How to interpret?
In equations, (f(n)) always stands for an
anonymous function g(n)  (f(n))
In the example above, (n
2
) stands for
3n
2
+ 2n + 1.

17. Comp 122asymp - 17
o-notation
f(n) becomes insignificant relative to g(n) as n
approaches infinity:
lim [f(n) / g(n)] = 0

n

g(n) is an upper bound for f(n) that is not
asymptotically tight.
Observe the difference in this definition from previous
ones. Why?
o(g(n)) = {f(n):  c > 0,  n
0
> 0 such that
 n 

n
0
, we have

0  f(n) < cg(n)}.
For a given function g(n), the set little-o:

18. Comp 122asymp - 18
(g(n)) = {f(n):  c > 0,  n
0
> 0 such that
 n 
n
0, we have
0  cg(n) < f(n)}.
 -notation
f(n) becomes arbitrarily large relative to g(n) as n
approaches infinity:
lim [f(n) / g(n)] = .

n

g(n) is a lower bound for f(n) that is not
asymptotically tight.
For a given function g(n), the set little-omega:

19. Comp 122asymp - 19
Comparison of Functions
f  g  a  b
f (n) = O(g(n))  a  b
f (n) = (g(n))  a  b
f (n) = (g(n))  a = b
f (n) = o(g(n))  a < b
f (n) = (g(n))  a > b

20. Comp 122asymp - 20
Limits
lim [f(n) / g(n)] = 0  f(n)  (g(n))

n
lim [f(n) / g(n)] <   f(n)  (g(n))

n
0 < lim [f(n) / g(n)] <   f(n)  (g(n))

n
0 < lim [f(n) / g(n)]  f(n) (g(n))

n
lim [f(n) / g(n)] =   f(n)  (g(n))

n
lim [f(n) / g(n)] undefined can’t say

n

21. Comp 122asymp - 21
Properties
Transitivity
f(n) = (g(n)) & g(n) = (h(n))  f(n) = (h(n))
f(n) = O(g(n)) & g(n) = O(h(n))  f(n) = O(h(n))
f(n) = (g(n)) & g(n) = (h(n))  f(n) = (h(n))
f(n) = o (g(n)) & g(n) = o (h(n))  f(n) = o (h(n))
f(n) = (g(n)) & g(n) = (h(n))  f(n) = (h(n))
Reflexivity
f(n) = (f(n))
f(n) = O(f(n))
f(n) = (f(n))

22. Comp 122asymp - 22
Properties
Symmetry
f(n) = (g(n)) iff g(n) = (f(n))
Complementarity
f(n) = O(g(n)) iff g(n) = (f(n))
f(n) = o(g(n)) iff g(n) = ((f(n))

23. August 3, 2024 Comp 122, Spring 2004
Common Functions

24. Comp 122asymp - 24
Monotonicity
f(n) is
monotonically increasing if m  n  f(m)  f(n).
monotonically decreasing if m  n  f(m)  f(n).
strictly increasing if m < n  f(m) < f(n).
strictly decreasing if m > n  f(m) > f(n).

25. Comp 122asymp - 25
Exponentials
Useful Identities:
Exponentials and polynomials
nmnm
mnnm
aaa
aa
a
a





)(
1
1
)(
0lim
nb
n
b
n
aon
a
n




26. Comp 122asymp - 26
Logarithms
x = log
b
a is the
exponent for a = b
x
.
Natural log: ln a = log
ea
Binary log: lg a = log
2a
lg
2
a = (lg a)
2
lg lg a

=

lg (lg a)
ac
a
b
bb
c
c
b
b
n
b
ccc
a
bb
b
ca
b
a
aa
b
a
a
ana
baab
ba
loglog
log
log
1
log
log)/1(log
log
log
log
loglog
loglog)(log








27. Comp 122asymp - 27
Logarithms and exponentials – Bases
If the base of a logarithm is changed from one
constant to another, the value is altered by a
constant factor.
Ex: log
10 n * log
210 = log
2 n.
Base of logarithm is not an issue in asymptotic
notation.
Exponentials with different bases differ by a
exponential factor (not a constant factor).
Ex: 2
n
= (2/3)
n
*3
n
.

28. Comp 122asymp - 28
Polylogarithms
For a  0, b > 0, lim
n ( lg
a
n / n
b
) = 0,
so lg
a
n = o(n
b
), and n
b
= (lg
a
n )
Prove using L’Hopital’s rule repeatedly
lg(n!) = (n lg n)
Prove using Stirling’s approximation (in the text) for lg(n!).

29. Comp 122asymp - 29
Exercise
Express functions in A in asymptotic notation using functions in B.
A B
5n
2
+ 100n 3n
2
+ 2
A  (n
2
), n
2
 (B)  A  (B)
log
3
(n
2
) log
2
(n
3
)
log
b
a = log
c
a / log
c
b; A = 2lgn / lg3, B = 3lgn, A/B =2/(3lg3)
n
lg4
3
lg n
a
log b
=

b
log a
; B =3
lg n
=n
lg 3
; A/B =n
lg(4/3)


 as n
lg
2
n

n
1/2
lim ( lg
a
n / n
b
) = 0 (here a = 2 and b = 1/2)  A  (B)

n
A  (B)
A  (B)
A  (B)
A  (B)

30. August 3, 2024 Comp 122, Spring 2004
Summations – Review

31. Comp 122asymp - 31
Review on Summations
Why do we need summation formulas?
For computing the running times of iterative
constructs (loops). (CLRS – Appendix A)
Example: Maximum Subvector
Given an array A[1…n] of numeric values (can be
positive, zero, and negative) determine the
subvector A[i…j] (1 i  j  n) whose sum of
elements is maximum over all subvectors.
1 -2 2 2

32. Comp 122asymp - 32
Review on Summations
MaxSubvector(A, n)
maxsum  0;
for i  1 to n
do for j = i to n
sum  0
for k  i to j
do sum += A[k]
maxsum  max(sum, maxsum)
return maxsum

n n j
T(n) =    1

i=1 j=i k=i
NOTE: This is not a simplified solution. What is the final answer?

33. Comp 122asymp - 33
Review on Summations
Constant Series: For integers a and b, a  b,
Linear Series (Arithmetic Series): For n  0,
Quadratic Series: For n  0,




b
ai
ab 11
2
)1(
21
1



nn
ni
n
i





n
i
nnn
ni
1
2222
6
)12)(1(
21 

34. Comp 122asymp - 34
Review on Summations
Cubic Series: For n  0,
Geometric Series: For real x  1,

For |x| < 1,





n
i
nn
ni
1
22
3333
4
)1(
21 






n
k
n
nk
x
x
xxxx
0
1
2
1
1
1 


 

0 1
1
k
k
x
x

35. Comp 122asymp - 35
Review on Summations
Linear-Geometric Series: For n  0, real c  1,
Harmonic Series: nth harmonic number, nI
+
,









n
i
nn
ni
c
cnccn
ncccic
1
2
21
2
)1(
)1(
2
n
H
n
1
3
1
2
1
1  



n
k
On
k
1
)1()ln(
1

36. Comp 122asymp - 36
Review on Summations
Telescoping Series:
Differentiating Series: For |x| < 1,


 
n
k
nkk aaaa
1
01



 

0
2
1k
k
x
x
kx

37. Comp 122asymp - 37
Review on Summations
Approximation by integrals:
For monotonically increasing f(n)
For monotonically decreasing f(n)
How?
  
 


n
m
n
mk
n
m
dxxfkfdxxf
1
1
)()()(
  

 

1
1
)()()(
n
m
n
mk
n
m
dxxfkfdxxf

38. Comp 122asymp - 38
Review on Summations
nth harmonic number




n
k
n
n
x
dx
k
1
1
1
)1ln(
1



n
k
n
n
x
dx
k
2 1
ln
1



n
k
n
k
1
1ln
1

39. Comp 122asymp - 39
Reading Assignment
Chapter 4 of CLRS.