代写代考 􏰀 Asymptotic Growth of Functions (CLRS Ch.3) 􏰀 Big-O, Big-Ω, Θ, little-o, l

􏰀 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 0, log(n) ∈ O(nε).
􏰀 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πn􏰗n􏰘n. 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 􏰚3􏰛n (logn)!, {(logn) , n }, 2 ,
2n, n · 2n, en, n!, (n!)2, (n2)!, 22n

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com