Scribd Logo
Upload

Welcome to Scribd!

  • 13 views

    Asymptotic

    Uploaded by

    bgpexpert
    This document discusses asymptotic analysis and growth rates of functions. It defines big-O notation (O), little-o notation (o), Omega (Ω), and Theta (Θ) and provides examples of how they describe the limiting behavior of functions. Polynomials, logarithmic functions, and exponential functions are specifically examined. The analysis of algorithms is also briefly discussed in terms of polynomial versus exponential running times.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    Asymptotic

    Uploaded by

    bgpexpert
    13 views19 pages
    This document discusses asymptotic analysis and growth rates of functions. It defines big-O notation (O), little-o notation (o), Omega (Ω), and Theta (Θ) and provides examples of how they describe the limiting behavior of functions. Polynomials, logarithmic functions, and exponential functions are specifically examined. The analysis of algorithms is also briefly discussed in terms of polynomial versus exponential running times.

    Original Title

    Asymptotic.pptx

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses asymptotic analysis and growth rates of functions. It defines big-O notation (O), little-o notation (o), Omega (Ω), and Theta (Θ) and provides examples of how they describe the limiting behavior of functions. Polynomials, logarithmic functions, and exponential functions are specifically examined. The analysis of algorithms is also briefly discussed in terms of polynomial versus exponential running times.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    13 views19 pages

    Asymptotic

    Uploaded by

    bgpexpert
    This document discusses asymptotic analysis and growth rates of functions. It defines big-O notation (O), little-o notation (o), Omega (Ω), and Theta (Θ) and provides examples of how they describe the limiting behavior of functions. Polynomials, logarithmic functions, and exponential functions are specifically examined. The analysis of algorithms is also briefly discussed in terms of polynomial versus exponential running times.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 19

    Growth Rates of Functions

    3/26/12
    Asymptotic Equivalence
    • Def:
    ⎛ f(n)⎞
    f (n) : g(n) iff lim n→ ∞ ⎜ ⎟ =1
    ⎝ g(n)⎠
    2 5 10 17
    For example, n +1: n
    2 2
    (think: , , , ,...)
    1 4 9 16

    Note that n2+1 is being used to name the


    function f such that f(n) = n2+1 for every n

    3/26/12
    An example: Stirling’s formula

    n
    ⎛n⎞
    n! : ⎜ ⎟ 2π n ("Stirling'sapproxim ation")
    ⎝e⎠

    3/26/12
    Little-Oh: f = o(g)
    • Def: f(n) = o(g(n)) iff

    f(n)
    lim =0
    n→ ∞ g(n)

    • For example, n2 = o(n3) since


    n 2
    1
    lim 3 = lim = 0
    n→ ∞ n n→ ∞ n
    3/26/12
    = o( ∙ ) is “all one symbol”
    • “f = o(g)” is really a strict partial order on
    functions
    • NEVER write “o(g) = f”, etc.

    3/26/12
    Big-Oh: O(∙)
    • Asymptotic Order of Growth:

    ⎛ f(n)⎞
    f (n) = O (g(n))iff lim ⎜ ⎟ <∞
    n→ ∞ ⎝ g(n)⎠

    • “f grows no faster than g”


    • A Weak Partial Order

    3/26/12
    Growth Order

    3n + n + 2 = O (n )because
    2 2

    3n + n + 2
    2
    lim = 3< ∞
    n→ ∞ n2

    3/26/12
    f = o(g) implies f = O(g)
    f(n)
    because if lim =0
    n→ ∞ g(n)

    f(n)
    then lim <∞
    n→ ∞ g(n)

    So forexam ple,n +1= O (n ) 2

    3/26/12
    Big-Omega
    • f = Ω(g) means g = O(f)
    • “f grows at least as quickly as g”

    3/26/12
    Big-Theta: 𝛩(∙)
    “Same order of growth”
    f (n) = Θ(g(n))
    iff
    f(n)= O (g(n))and g(n)= O (f(n))
    orequivalently
    f(n)= O (g(n))and f(n)= Ω(g(n))
    So, for example,
    3n + 2 = Θ(n )
    2 2

    3/26/12
    Rough Paraphrase
    • f∼g: f and g grow to be roughly equal
    • f=o(g): f grows more slowly than g
    • f=O(g): f grows at most as quickly as g
    • f=Ω(g): f grows at least as quickly as g
    • f=𝛩(g): f and g grow at the same rate

    3/26/12
    Equivalent Defn of O(∙)
    “From some point on, the value of f
    is at most a constant multiple of the
    value of g”

    f (n) = O (g(n))iff
    ∃c,n0 such that∀n ≥n0 :
    f(n)≤c⋅g(n)

    3/26/12
    Three Concrete Examples
    • Polynomials
    • Logarithmic functions
    • Exponential functions

    3/26/12
    Polynomials
    • A (univariate) polynomial is a function such as f(n) =
    3n5+2n2-n+2 (for all natural numbers n)
    • This is a polynomial of degree 5 (the largest
    exponent)
    d
    • Or in general f (n) = ∑cini
    i=0
    • Theorem:
    – If a<b then any polynomial of degree a is o(any
    polynomial of degree b)
    – If a≤b then any polynomial of degree a is O(any
    polynomial of degree b)
    3/26/12
    Logarithmic Functions
    • A function f is logarithmic if it is Θ(logbn) for
    some constant b.
    • Theorem: All logarithmic functions are Θ() of
    each other, and are Θ(any logarithmic function
    of a polynomial)
    • Theorem: Any logarithmic function is o(any
    polynomial)

    3/26/12
    Exponential Functions
    • A function is exponential if it is Θ(cn) for some
    constant c>1.
    • Theorem: Any polynomial is o(any
    exponential)
    • If c<d then cn=o(dn).

    3/26/12
    Growth Rates and Analysis of Algorithms

    • Let f(n) measure the amount of time taken by an


    algorithm to solve a problem of size n.
    • Most practical algorithms have polynomial
    running times
    • E.g. sorting algorithms generally have running
    times that are quadratic (polynomial or degree 2)
    or less (for example, O(n log n)).
    • Exhaustive search over an exponentially growing
    set of possible answers requires exponential time.
    3/26/12
    Another way to look at it
    • Suppose an algorithm can solve a problem of size S in time T
    and you give it twice as much time.
    • If the running time is f(n)=n2, so that T=S2, then in time 2T you
    can solve a problem of size (21/2)∙S
    • If the running time is f(n)=2n, so that T=2S, then in time 2T you
    can solve a problem of size S+1.
    • In general doubling the time available to a polynomial
    algorithm results in a MULTIPLICATIVE increase in the size
    of the problem that can be solved
    • But doubling the time available to an exponential algorithm
    results in an ADDITIVE increase to the size of the problem
    that can be solved.
    3/26/12
    FINIS

    3/26/12

    You might also like