Scribd Logo
Upload

Welcome to Scribd!

  • 75 views

    Algorithm Evaluation

    Uploaded by

    Nabila Najat
    The document discusses algorithm evaluation and complexity analysis using Big O notation. It provides examples of common algorithms like linear search, binary search, and various sorting algorithms. Their time complexities are given as O(n) for linear search, O(log2n) for binary search, O(n2) for bubble and selection sort, and O(n log2n) for quicksort. It also discusses reducing complexities by ignoring constants and lower order terms for large input sizes n.

    Copyright:

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

    Algorithm Evaluation

    Uploaded by

    Nabila Najat
    75 views18 pages
    The document discusses algorithm evaluation and complexity analysis using Big O notation. It provides examples of common algorithms like linear search, binary search, and various sorting algorithms. Their time complexities are given as O(n) for linear search, O(log2n) for binary search, O(n2) for bubble and selection sort, and O(n log2n) for quicksort. It also discusses reducing complexities by ignoring constants and lower order terms for large input sizes n.

    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?

    The document discusses algorithm evaluation and complexity analysis using Big O notation. It provides examples of common algorithms like linear search, binary search, and various sorting algorithms. Their time complexities are given as O(n) for linear search, O(log2n) for binary search, O(n2) for bubble and selection sort, and O(n log2n) for quicksort. It also discusses reducing complexities by ignoring constants and lower order terms for large input sizes n.

    Copyright:

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

    Algorithm Evaluation

    Uploaded by

    Nabila Najat
    The document discusses algorithm evaluation and complexity analysis using Big O notation. It provides examples of common algorithms like linear search, binary search, and various sorting algorithms. Their time complexities are given as O(n) for linear search, O(log2n) for binary search, O(n2) for bubble and selection sort, and O(n log2n) for quicksort. It also discusses reducing complexities by ignoring constants and lower order terms for large input sizes n.

    Copyright:

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

    Algorithm Evaluation

    Whats an algorithm?

    a clearly specified set of simple instructions to be followed to solve a problem a way of doing something What are some different search algorithms? What are some different sorting algorithms?

    How good is it?

    Measure performance by measuring resource usage


    time space

    Space should be consistent across different machines, but what about time?

    What if you ran an algorithm on both a Intel Pentium II and an Intel Core Duo 2?

    How many comparisons?

    Assume an array containing n=10 elements: 4, 2, 62, 6, 78, 8, 5, 91, 63, 13


    Using the linear search algorithm:

    How many comparisons would we need to find something at the beginning (e.g., 4)? On average how many comparisons would we need to find something in the middle? How many comparisons would we need to find something at the end (e.g., 13)?

    Linear Search Evaluation

    Assuming an array of n elements, linear search yields:


    Best case: 1 comparison Average case: n/2 comparisons Worst case: n comparisons

    Big O!

    a mathematical representation of the complexity of an algorithm on the order of... usually used to estimate the upper bound performance O( # comparisons ) or O( # operations ) or O( # of times things happen)

    Summary of Complexities
    O(1) : constant time not related to length of data set O(log2n) : log time and is fast O(n) : linear time O(n log2n) : n log n time O(n2) : quadratic time, polynomial complexity O(n3) : cubic time, polynomial complexity O(nn) : not computable

    A Simple Example
    k = 0; for (int i = 0; i < n; i++) k++;
    Whats my complexity?!? (Hint: use Big O notation) ...on the order of...

    A Simpler Example
    k = 0; k++; Whats my complexity?!? (Hint: use Big O notation)
    ...on the order of...

    Another Example
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) for (int k = 0; k < n; k++) a++;
    Whats my complexity?!? (Hint: use Big O notation) ...on the order of...

    ::sigh:: Another Example


    k = 0; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) k++;
    Whats my complexity?!? (Hint: use Big O notation) ...on the order of...

    Rules of Thumb

    one loop O(n) two nested loops O(n2) three nested loops O(n3)

    Back to linear search...

    Best case: 1 comparison O(1) Worst case: n comparisons O(n) Average case: n/2 comparisons
    ...wait...what if n is really, really, really big?

    O(n/2) reduces to O(n)

    Linear searchs complexity is O(n)

    Complexity Reduction

    Rules of thumb:

    consider LARGE values of n removes constants larger complexities overshadow smaller ones removes smaller Os

    Examples:
    O(n/2) O(n) O(2*n) O(n) O(n + 5) O(n) O(n + 209502) O(n) O(n2) + O(n) O(n2 + n) O(n2)

    Reduction Example
    k = 0; for (int i = 0; i < n/2; i++) k++;

    Notice the n/2! Whats the complexity?

    Binary Search Algorithm

    Assume a sorted array containing n=10 elements: 2, 4, 5, 6, 8, 13, 62, 63, 78, 91
    Using the binary search algorithm: What is the best case performance?

    What is the worst case performance? What is the O complexity?

    Summary of Common Complexities


    linear search : O(n) binary search : O(log2n) bubble sort : O(n2) selection sort : O(n2) quick sort : O(n log2n)

    IB Expectations

    Know the complexities of the aforementioned algorithms Given a new algorithm or snippet of code, figure out its complexity

    You might also like