Asymptotic Growth of Functions (CLRS Ch.3) Big-O, Big-Ω, Θ, little-o, little-ω
Topic 3: Asymptotic Runtime
Topic 3: Asymptotic Notations
Copyright By PowCoder代写 加微信 powcoder
Asymptotic notation for Growth of Functions: Motivations
Analysis of algorithms becomes analysis of functions
The (WC) running time of InsertionSort is characterized by a
quadratic function f (n) = an2 + bn + c
For some sort algorithms (e.g., mergeSort, later) the running time is
g(n) = cn log n.
Which algorithm runs faster? In what sense?
Topic 3: Asymptotic Notations
Asymptotic notation for Growth of Functions: Motivations
To simplify algorithm analysis, want function notation which indicates rate of growth (a.k.a., order of complexity), and denotes a set of functions
O(f(n)) — read as “big O of f(n)”
Ω(f(n)) — read as “big Omega of f(n)”
Θ(f(n)) — read as “Theta of f(n)”
o(f(n)) — read as “little o of f(n)”
ω(f(n)) — read as “little omega of f(n)”
Big-O Notation: O(f(n))
(Roughly) The set of functions which, as n gets large, grow no faster than a constant times f(n).
Definition: A function h(n) : N → R belongs to O(f(n)) if there existconstantsc>0andn0 ∈Nsuchthatforalln≥n0 itholds that 0 ≤ h(n) ≤ cf(n) (we can omit “0 ≤ ” in the sequel).
Examples:
482n2 ∈ O(n2) 482n2 ∈ O(n3) 482n2 ∈ O(n2.5) 482n2 ∈ O(n2.001) n3 + 255n2 + n2.999 ∈ O(n3)
5n, n≤10120 2 h(n)= n2, n>10120 ∈O(n)
Topic 3: Asymptotic Notations
Big-O Notation: O(f(n))
Inverse: A function h(n) ∈/ O(f(n)) if no matter what c > 0 and n0 ∈ N we choose, we can always find a large enough n > n0 s.t. h(n) > cf(n). That is, h is NOT upper bounded by f within a constant factor.
[Examples:]
482n2 ∈/ O(n) 1 n2 ∈/ O(n1.99999) 482
n2 ∈/O(np)foranyp<2
n3 + 255n2 + n2.999 ∈/ O(n2.99999)
n2, niseven 2 h(n)= n3, nisodd ∈/O(n)
Topic 3: Asymptotic Notations
The class of constant functions is expressed by O(1). The notation comes from O(n0) for degree-0 polynomial.
Definitions
O(f(n)) is the set of functions h(n) that
roughly, grow no faster than f(n)
Formally: h(n) ∈ O(f(n)) if ∃c > 0,n0 ∈ N, such that for all
n≥n0 wehaveh(n)≤cf(n).
Ω(f(n)) is the set of functions h(n) that
roughly, grow at least as fast as f(n)
Formally: h(n) ∈ Ω(f(n)) if ∃c > 0,n0 ∈ N, such that for all
n≥n0 wehaveh(n)≥cf(n).
h(n) ∈ Ω(f(n)) if and only if f(n) ∈ O(h(n))
Θ(f(n)) is the set of functions h(n) that
roughly, grow at the same rate as f(n)
Formally: h(n) ∈ Θ(f(n)) if ∃c0 > 0,c1 > 0,n0 ∈ N, such that
for all n ≥ n0 we have c0f(n) ≤ h(n) ≤ c1f(n).
Θ(f(n))=O(f(n))∩Ω(f(n))
Topic 3: Asymptotic Notations
Definitions (Cont’d):
o(f(n)) is the set of functions h(n) that
roughly, grow strictly slower than f(n)
Formally: h(n) ∈ o(f(n)) if limn→∞ h(n) = 0 f (n)
f (n) Subset of O(f(n))
ω(f(n)) is the set of functions h(n) that
roughly, grow strictly faster than f(n)
Formally: h(n) ∈ ω(f(n)) if limn→∞ h(n) = ∞ f (n)
Topic 3: Asymptotic Notations
I.e. for every ε > 0, there exists nε ∈ N such that for every n≥nε itholdsthat h(n) <ε
I.e. for every M > 0, there exists nM ∈ N such that for all n≥nM itholdsthat h(n) >M.
h(n) ∈ ω(f(n)) if and only if f(n) ∈ o(h(n))
Subset of Ω(f(n))
the textbook overloads “=”
Textbook uses g(n) = O(f(n))
But we define O(f(n)) as a set of functions. Both are by now correct
My advice: use g(n) ∈ O(f(n)).
Which of the following belongs to O(n3), Ω(n3), Θ(n3), o(n3), ω(n3) ?
1. f1(n) = 19n
2. f2(n) = 77n2
3. f3(n) = 6n3 + n2 log n 4. f4(n) = 11n4
Topic 3: Asymptotic Notations
f1,f2,f3 ∈O(n3) f1(n)≤19n3,foralln≥0—c0 =19,n0 =0 f2(n)≤77n3,foralln≥0—c0 =77,n0 =0 f3(n) ≤ 6n3 + n2 · n, for all n ≥ 1, since log n ≤ n
f3,f4 ∈Ω(n3)
f3(n) ≥ 6n3, for all n ≥ 1, since n2 log n ≥ 0 f4(n) ≥ 11n3, for all n ≥ 0
Topic 3: Asymptotic Notations
Answers (Cont’d):
f3 ∈ Θ(n3) (why?)
f1,f2 ∈o(n3)
f (n): lim 19n =lim 19 =0
1 n→∞ n3 n→∞ n2
f (n): lim 77n2 =lim 77 =0 2 n→∞ n3 n→∞ n
f(n):lim 6n3+n2logn =lim 6+logn =6 3 n→∞ n3 n→∞ n
f (n): lim 11n4 =lim 11n=∞ 4 n→∞ n3 n→∞
f4 ∈ ω(n3)
Topic 3: Asymptotic Notations
More big-O Notation Properties
Reflexivity: For any function f it holds that f(n) ∈ O(f(n)) (the same
goes for Ω(·), Θ(·))
Additivity: If f(n),g(n)∈O(h(n)) then f(n)+g(n)∈ O(h(n)) (same goes for all other notations; the same holds for any constant number of functions)
BUT doesn’t hold in general if the number of functions to be added is not fixed, e.g., consider f (n) + f (n) + … + f (n). When f (n) ∈ O(h(n)), the
function that adds f(n) to itself n times may not be in O(h(n)), e.g., letting f(n) = h(n) = n.
Multiplicative: If f1(n) ∈ O(f2(n)) and g1(n) ∈ O(g2(n)) and all functions take only positive values, then f1(n) · g1(n) ∈ O(f2 · g2) (same goes for all other notations)
Transitivity: if f(n) ∈ O(g(n)) and g(n) ∈ O(h(n)) then f(n) ∈ O(h(n)) (same goes for all other notations!)
BUT if f(n) ∈ O(h(n)) and g(n) ∈ O(h(n)) then f and g may not be comparable…
Topic 3: Asymptotic Notations
Logarithm Review (CLRS : p56)
For any b > 1 and n > 0 we define
Definition of logb(n): blogb n = n
logb n as a function in n: increasing, one-to-one ln n = loge n (natural logarithm)
lg n = log2 n (base 2, binary)
Foranyxandanyp,logbxp =plogbx
For any x and any y, logb(xy) = logb x+logb y Foranyxandanyy,xlogby =ylogbx
Foranyxandanyc>1,logbx=(logbc)(logcx) Foranyb>1wehaveΘ(logbn)=Θ(logn)
(log n)k ∈ o(nε), for any fixed positives k and ε
Topic 3: Asymptotic Notations
Handy ‘big O’ tips:
h(n) ∈ O(f(n)) if and only if f(n) ∈ Ω(h(n))
h(n) ∈ o(f(n)) if and only if f(n) ∈ ω(h(n))
limit rules: if limn→∞ h(n) exists then f (n)
limit = ∞, then h ∈ Ω(f),ω(f)
limit=kforsome0
Moreover, for any fixed ε > 0, we can show log(n) ∈ O(n 2ε ). Since
n2ε ∈ o(nε) we get log(n) ∈ o(nε).
And if h is a monotone non-decreasing function then we also have
h(f(n)) ≥ h(g(n)).
So since ∀n,n ≤ n2, then ∀n,√n ≤ n, then ∀n ≥ 1,log(n) ≤ log(n),
Topic 3: Asymptotic Notations
then ∀n ≥ 1,2 log(n) ≤ 2log(n) = n for every n, so 2 log(n) ∈ O(n).
O(·), Ω(·), Θ(·), o(·), ω(·) – JUST useful asymptotic notations
Topic 3: Asymptotic Notations
Another useful formula is Stirling’s Approximation: n! ≈ √2πnnn. e
Example: The following functions are ordered in increasing order of growth (each is in big-Oh of next one). Those in the same group are in big-Theta of each other.
{n1/ log n, 1}, log∗(n), {log log n, ln ln n}, log n, ln n,
√ logn logn 2 3
, ( 2) , 2 , {nlogn, log(n!)}, n, {n, 8
logn loglogn 3n (logn)!, {(logn) , n }, 2 ,
2n, n · 2n, en, n!, (n!)2, (n2)!, 22n
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com