Scribd Logo
Upload

Welcome to Scribd!

  • 232 views

    Algorithm Analysis

    Uploaded by

    pieroom
    This document discusses algorithm analysis and efficiency. It covers: 1) How to analyze the efficiency of algorithms both empirically by testing on examples, and theoretically by determining resource needs mathematically. 2) How to determine an algorithm's order of growth or running time by ignoring constants and looking at how processing time increases with larger inputs. 3) Common time complexities like constant O(1), logarithmic O(log n), linear O(n), quadratic O(n^2), and cubic O(n^3) time. 4) Rules for analyzing loops and nested loops to determine overall time complexity based on number of iterations.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd

    Algorithm Analysis

    Uploaded by

    pieroom
    232 views14 pages
    This document discusses algorithm analysis and efficiency. It covers: 1) How to analyze the efficiency of algorithms both empirically by testing on examples, and theoretically by determining resource needs mathematically. 2) How to determine an algorithm's order of growth or running time by ignoring constants and looking at how processing time increases with larger inputs. 3) Common time complexities like constant O(1), logarithmic O(log n), linear O(n), quadratic O(n^2), and cubic O(n^3) time. 4) Rules for analyzing loops and nested loops to determine overall time complexity based on number of iterations.

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses algorithm analysis and efficiency. It covers: 1) How to analyze the efficiency of algorithms both empirically by testing on examples, and theoretically by determining resource needs mathematically. 2) How to determine an algorithm's order of growth or running time by ignoring constants and looking at how processing time increases with larger inputs. 3) Common time complexities like constant O(1), logarithmic O(log n), linear O(n), quadratic O(n^2), and cubic O(n^3) time. 4) Rules for analyzing loops and nested loops to determine overall time complexity based on number of iterations.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    232 views14 pages

    Algorithm Analysis

    Uploaded by

    pieroom
    This document discusses algorithm analysis and efficiency. It covers: 1) How to analyze the efficiency of algorithms both empirically by testing on examples, and theoretically by determining resource needs mathematically. 2) How to determine an algorithm's order of growth or running time by ignoring constants and looking at how processing time increases with larger inputs. 3) Common time complexities like constant O(1), logarithmic O(log n), linear O(n), quadratic O(n^2), and cubic O(n^3) time. 4) Rules for analyzing loops and nested loops to determine overall time complexity based on number of iterations.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    of 14
    At a glance
    Powered by AI
    The key takeaways are that algorithms can be analyzed both empirically by implementing them and theoretically by determining resource needs mathematically, and efficiency is important when analyzing algorithms.

    Algorithms can be analyzed empirically by implementing competing algorithms and testing them on different inputs, or theoretically by mathematically determining the resources like running time and memory needed. Resources that are analyzed include running time, memory usage, and communication bandwidth.

    The different orders of growth analyzed are big O notation which provides an upper bound, Omega notation which provides a lower bound, and Theta notation which provides a tight bound. Orders of growth include constant, logarithmic, linear, quadratic, cubic, exponential, and more.

    Algorithm Analysis

    Lectures 3 & 4

    Resources
    Data Structures & Algorithms Analysis in C++
    (MAW): Chap. 2
    Introduction to Algorithms (Cormen, Leiserson, &
    Rivest): Chap.1
    Algorithms Theory & Practice (Brassard & Bratley):
    Chap. 1
    Algorithms
    • An algorithm is a well-defined
    computational procedure that takes
    some value or a set of values, as input
    and produces some value, or a set of
    values as output.
    • Or, an algorithm is a well-specified set
    of instructions to be solve a problem.
    Efficiency of Algorithms
    • Empirical
    – Programming competing algorithms and
    trying them on different instances
    • Theoretical
    – Determining mathematically the quantity of
    resources (execution time, memory space,
    etc) needed by each algorithm
    Analyzing Algorithms
    • Predicting the resources that the algorithm
    requires:
    • Computational running time
    • Memory usage
    • Communication bandwidth
    • The running time of an algorithm
    • Number of primitive operations on a particular input size
    • Depends on
    – Input size (e.g. 60 elements vs. 70000)
    – The input itself ( partially sorted input for a sorting
    algorithm)
    Order of Growth
    • The order (rate) of growth of a running
    time
    – Ignore machine dependant constants
    – Look at growth of T(n) as n→∞
    Θ notation
    • Drop low-order terms
    • Ignore leading constants
    • E.g.
    – 3n3 + 90n2 – 2n +5 = Θ (n3)
    Mathematical Background
    Mathematical Background
    • Definitions:
    – T(N) = O(f(N)) iff ∃ c and n0 ∋
    T(N) ≤ c.f(N) when N ≥ n0
    – T(N) = Ω (g(N)) iff ∃ c and n0 ∋
    T(N) ≥ c.g(N) when N ≥ n0
    – T(N) = Θ (h(N)) iff T(N) = O(h(N)) and
    T(N) = Ω (h(N))
    Mathematical Background
    • Definitions:
    – T(N) = o(f(N)) iff ∃ c and n0 ∋
    T(N) < c.f(N) when N ≥ n0

    – T(N) = ω (g(N)) iff ∃ c and n0 ∋


    T(N) > c.g(N) when N ≥ n0
    Mathematical Background
    • Rules:
    – If T1(N) = O(f(N)) and T2(N) = O(g(N)) then
    a) T1(N) + T2(N) = max( O(f(N)),O(g(N))
    b) T1(N) * T2(N) = O(f(N) * g(N))

    – If T(N) is a polynomial of degree k, then T(N) =


    Θ (Nk)
    – Logk N = O(N) for any constant k.
    More …
    1. 3n3 + 90n2 – 2n +5 = O(n3 )
    2. 2n2 + 3n +1000000 = Θ (n2)
    3. 2n = o(n2) ( set membership)
    4. 3n2 = O(n2) tighter Θ (n2)
    5. n log n = O(n2)
    6. True or false:
    – n2 = O(n3 )
    – n3 = O(n2)
    – 2n+1= O(2n)
    – (n+1)! = O(n!)
    Ranking by Order of
    Growth2 k
    1 n n log n n n

    (3/2)n 2n (n)! (n+1)!


    Running time calculations
    • Rule 1 – For Loops
    The running time of a for loop is at most the
    running time of the statement inside the for loop
    (including tests) times the number of iterations

    • Rule 2 – Nested Loops


    Analyze these inside out. The total running time of a
    statement inside a group of nested loops is the
    running time of the statement multiplied by the
    product of the sizes of all the loops
    Running time calculations:
    Examples
    Example 1:
    sum = 0;
    for (i=1; i <=n; i++)
    sum += n;
    Example 2:
    sum = 0;
    for (j=1; j<=n; j++)
    for (i=1; i<=j; i++)
    sum++;
    for (k=0; k<n; k++)
    A[k] = k;
    How to rank?

    You might also like