Asymptotic Analysis CLRS, Sections 3.1 3.2 Asymptotic Complexity

Asymptotic Analysis CLRS, Sections 3.1  3.2 Asymptotic Complexity

Asymptotic Analysis CLRS, Sections 3.1 3.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. Describes behavior of function in the limit. Written using Asymptotic Notation. CS 321 - Data Structures 2 Asymptotic Notation , O, , o, Defined for functions over the natural numbers. Ex: f(n) = (n2). Describes how f(n) grows in comparison to n2.

Defines a set of functions; in practice used to compare growth rate of two functions. The notations describe the relationship between the defining function and a defined set of functions. CS 321 - Data Structures 3 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)) CS 321 - Data Structures 4 -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)) CS 321 - Data Structures

5 -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 c1g(n) n0, we have 0 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). CS 321 - Data Structures 6

Relationship Between , O, CS 321 - Data Structures 7 Relationship Between , , O Theorem Theorem :: For For any any two two functions functions g(n) g(n) and and f(n), f(n), f(n) f(n) == (g(n)) (g(n)) iff iff f(n)

f(n) == O(g(n)) O(g(n)) and and f(n) f(n) == (g(n)). (g(n)). (g(n)) = O(g(n)) (g(n)) In practice, asymptotically tight bounds are obtained from asymptotic upper and lower bounds. CS 321 - Data Structures 8 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)}. Intuitively: Set of all functions whose rate of growth is lower than that of g(n).

g(n) is an upper bound for f(n)that is not asymptotically tight. CS 321 - Data Structures 9 -notation For a given function g(n), the set little-omega: (g(n)) = {f(n): c > 0, n0 > 0 such that n n0, we have 0 cg(n) < f(n)}. Intuitively: Set of all functions whose rate of growth is higher than that of g(n). g(n) is a lower bound for f(n) that is not asymptotically tight. CS 321 - Data Structures 10 Comparison of Functions

f g f f f f f (n) (n) (n) (n) (n) = = = = = ~ O(g(n))

(g(n)) (g(n)) o(g(n)) (g(n)) a b ~ ~ ~ ~ ~ a a a a a CS 321 - Data Structures b

b = b < b > b 11 Limit Definitions of Asymptotic Notations o-notation (little-o): f(n) becomes insignificant relative to g(n) as n approaches infinity: lim [f(n) / g(n)] = 0 n -notation (little-omega): f(n) becomes arbitrarily large relative to g(n) as n approaches infinity: lim [f(n) / g(n)] = n

CS 321 - Data Structures 12 Limit Definitions of Asymptotic Notations -notation (Big-theta): f(n) relative to g(n)equals a constant, c, which is greater than 0 and less than infinity as n approaches infinity: 0 < lim [f(n) / g(n)] < n CS 321 - Data Structures 13 Limit Definitions of Asymptotic Notations O-notation (Big-o): f(n) O(g(n)) f(n) (g(n))and f(n) o(g(n))

f(n) relative to g(n)equals some value less than infinity as n approaches infinity: lim [f(n) / g(n)] < n -notation (Big-omega): f(n) (g(n)) f(n) (g(n))and f(n) (g(n)) f(n) relative to g(n)equals some value greater than 0 as n approaches infinity: 0 < lim [f(n) / g(n)] n CS 321 - Data Structures 14 Examples Use limit definitions to prove: 10n - 3n O(n2) 3n4 (n3)

n2/2 - 3n (n2) 22n (2n) CS 321 - Data Structures 15 Examples Use limit definitions to prove: 10n - 3n O(n2) Yes! lim [ 10n - 3n / n2 ] = 0 n 3n4 (n3) Yes! lim [ 3n4 / n3 ] = n

n2/2 - 3n (n2) Yes! lim [ n2/2 - 3n / n2 ] = 1/2 n 22n (2n) No! lim [ 22n / 2n ] = n CS 321 - Data Structures 16 Why Do We Care? CS 321 - Data Structures 17

Complexity and Tractability T(n) n 10 20 30 40 50 100 103 104 105 106 n n log n n2 .01ms .03ms .1ms .02ms .09ms

.4ms .03ms .15ms .9ms .04ms .21ms 1.6ms .05ms .28ms 2.5mms .1ms .66ms 10ms 1ms 9.96ms 1ms 10ms 130ms 100ms 100ms 1.66ms 10s 1ms 19.92ms 16.67m n3

n4 1ms 10ms 8ms 160ms 27ms 810ms 64ms 2.56ms 125mms 6.25ms 1ms 100ms 1s 16.67m 16.67m 115.7d 11.57d 3171y 31.71y 3.17107y n10

10s 2.84h 6.83d 121d 3.1y 3171y 3.171013y 3.171023y 3.171033y 3.171043y 2n 1ms 1ms 1s 18m 13d 41013y 3210283y Assuming the microprocessor performs 1 billion ops/s. CS 321 - Data Structures

18 CS 321 - Data Structures 19

Recently Viewed Presentations

  • Slide pack for PPI Workshops

    Slide pack for PPI Workshops

    NHS England 2017, p 31, update on the Forward View. Integrated Care Systems lead, plan, commission care for local populations. They bring together commissioners, providers and local authorities to provide local healthcare and system leadership. Emphasis is on Partnership between...
  • Master ASL 8 - Chandler Unified School District

    Master ASL 8 - Chandler Unified School District

    Master ASL 8 Describing People Objectives To describe people's physical appearances To describe personality traits and characteristics To improve ASL narrative skills To learn about Deaf-Blind communication To discuss health issues To describe the natural world and environment Picture it…
  • The Screech Owl Who Liked Television

    The Screech Owl Who Liked Television

    for years to come and are anxious to share it with anyone who will listen. Utter. Utter . is a multiple meaning word. It can also mean total, as in the sentence When the lights went out the city was...
  • Fingerprint Analysis - West Linn-Wilsonville School District

    Fingerprint Analysis - West Linn-Wilsonville School District

    The DOUBLE LOOP is made up of any two loops combined into one fingerprint. The Double Loop - ridge count. Count the ridges that cross a line drawn between the delta. The Plain Whorl. These have at least one ridge...
  • The Hypotenuse &amp; Peace - LAWR

    The Hypotenuse & Peace - LAWR

    Conflict power laws. ... 50-50no holes. level zero. Our Lord Jesus Christ. the . way, the truth, and the life. the. hypotenuse . is indeed the path of . peace! The unique geometric solution. only straight and solid condition without...
  • Hyatt Regency Walkway Collapse - OpenStax CNX

    Hyatt Regency Walkway Collapse - OpenStax CNX

    Atrium roof collapse. November 1979. Seiden-Page investigates collapse and carries out "a thorough design check" of all elements of atrium roof. Assures owners of overall safety of newly designed roof.
  • Formal Charge and Bond Energy

    Formal Charge and Bond Energy

    Bond energies can be used to calculate an approximate energy of reaction H can be thought of as the energies required to break old bonds plus the energies released when new bonds are formed H = D(bonds broken) - D(bonds...
  • Why Value-Added? - VARC

    Why Value-Added? - VARC

    This Oak Tree Analogy was created to introduce the concept of value added calculations. It is not in the education context in an attempt to keep this overview of the theory of value added separate from details specific to its...