Asymptotic
Asymptotic Notations
Notations
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.
● Describes behavior of function in the limit.
● Written using Asymptotic Notation.
Asymptotic Notation
● Q, O, W, o, w
● Defined for functions over the natural numbers.
○ Ex: f(n) = Q(n2).
○ Describes how f(n) grows in comparison to n2.
● 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.
-notation For function g(n), we define (g(n)),
big-Theta of n, as the set:
(g(n)) = {f(n) :
positive constants c1, c2, and n0,
such that n n0,
we have 0 < c1g(n) f(n) c2g(n)
}
Intuitively: Set of all functions that
have the same rate of growth as g(n).
g(n) is an asymptotically tight bound for f(n).
Example
(g(n)) = {f(n) : positive constants c1, c2, and n0,
such that n n0, 0 < c1g(n) f(n) c2g(n)}
● 10n2 - 3n = Q(n2)
● What constants for n0, c1, and c2 will work?
● Make c1 a little smaller than the leading coefficient, and
c2 a little bigger.
● To compare orders of growth, look at the leading term.
● Exercise: Prove that (n2/2)-3n= Q(n2)
O-notation
For function g(n), we define O(g(n)),
big-O of n, as the set:
O(g(n)) = {f(n) :
positive constants c and n0, such that n n0,
we have 0 < f(n) cg(n) }
Intuitively: Set of all functions whose rate of growth is the
same as or lower than that of g(n).
g(n) is an asymptotic upper bound for f(n).
f(n) = (g(n)) f(n) = O(g(n)).
(g(n)) O(g(n)).
-notation
For function g(n), we define (g(n)), big-Omega
of n, as the set:
(g(n)) = {f(n) :
positive constants c and n0, such that n n0,
we have 0 < cg(n) f(n)}
Intuitively: Set of all functions
whose rate of growth is the same
as or higher than that of g(n).
g(n) is an asymptotic lower bound for f(n).
f(n) = (g(n)) f(n) = (g(n)).
(g(n)) (g(n)).
Relations Between Q, O, W
limn→∞ f(n)/g(n) = c; =c >0 and c< ∞ ⇒ f = Θ(g)
limn→∞ f(n)/g(n) = c; c < ∞ ⇒ f = O(g)
limn→∞ f(n)/g(n) =c; c > 0 ⇒ f = Ω(g)
o-notation
For a given function g(n), the set little-o:
o(g(n)) = {f(n): c > 0, n0 > 0 such that
n n0, we have 0 < f(n) < cg(n)}.
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.
w -notation
For a given function g(n), the set little-omega:
w(g(n)) = {f(n): c > 0, n > 0 such that
0
n n0, we have 0 < cg(n) < f(n)}.
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.
STANDART NOTATIONS AND COMMON
FUNTIONS
Floor and ceiling functions are monotonically increasing functions.
EXPONENTIALS
Logarithms
Definition:
2 y x y log 2 ( x)
Properties:
x1 x2 log( x1 ) log( x2 )
log( x1 ) log( x2 ) x1 x2
log(1) 0
log( x1 x2 ) log( x1 ) log( x2 )
log( x a ) a log( x)
log(x1 )
x1log(x2 ) x2
Summations
n
n(n 1)
i
i 1 2
( n 2 )
n
n(n 1)( 2n 1)
i2
i 1 6
( n 3 )
n
n ( k 1) n k
i 1
i
k
k 1 2
... (n k 1 )
2
i 0
i
2 n 1
1
n
a n 1 1
i 0
a
i
a 1
Order of growth
● Principal interest is to determine
○ how running time grows with input size – Order of growth.
○ the running time for large inputs – Asymptotic complexity.
● In determining the above,
○ Lower-order terms and coefficient of the highest-order term are insignificant.
○ Ex: In 7n5+6n3+n+10, which term dominates the running time for very large n?
● Complexity of an algorithm is denoted by the highest-order term in the expression for running
time.
○ Constant complexity when running time is independent of the input size – denoted.
Exercises
