Scribd Logo
Upload

Welcome to Scribd!

  • 7 views

    Asymptotic Blunders: Should Say

    Uploaded by

    Kariem Mohamed Ragab Hamed
    This document discusses common mistakes made when using big O notation to analyze the asymptotic behavior of algorithms. It provides five examples of incorrect uses of big O notation: 1) writing O(g) = f, 2) claiming a lower bound using "at least" rather than an equality, 3) falsely representing a summation as a lower order term, 4) providing a false proof for a summation, 5) making an incorrect claim about a summation using big O notation. The document emphasizes that big O notation defines a relation, not an equality.

    Copyright:

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

    Asymptotic Blunders: Should Say

    Uploaded by

    Kariem Mohamed Ragab Hamed
    7 views3 pages
    This document discusses common mistakes made when using big O notation to analyze the asymptotic behavior of algorithms. It provides five examples of incorrect uses of big O notation: 1) writing O(g) = f, 2) claiming a lower bound using "at least" rather than an equality, 3) falsely representing a summation as a lower order term, 4) providing a false proof for a summation, 5) making an incorrect claim about a summation using big O notation. The document emphasizes that big O notation defines a relation, not an equality.

    Original Description:

    blunders

    Original Title

    MIT6_042JS16_AsymBlunders

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses common mistakes made when using big O notation to analyze the asymptotic behavior of algorithms. It provides five examples of incorrect uses of big O notation: 1) writing O(g) = f, 2) claiming a lower bound using "at least" rather than an equality, 3) falsely representing a summation as a lower order term, 4) providing a false proof for a summation, 5) making an incorrect claim about a summation using big O notation. The document emphasizes that big O notation defines a relation, not an equality.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    7 views3 pages

    Asymptotic Blunders: Should Say

    Uploaded by

    Kariem Mohamed Ragab Hamed
    This document discusses common mistakes made when using big O notation to analyze the asymptotic behavior of algorithms. It provides five examples of incorrect uses of big O notation: 1) writing O(g) = f, 2) claiming a lower bound using "at least" rather than an equality, 3) falsely representing a summation as a lower order term, 4) providing a false proof for a summation, 5) making an incorrect claim about a summation using big O notation. The document emphasizes that big O notation defines a relation, not an equality.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 3

    Mathematics for Computer Science Big Oh Mistakes

    MIT 6.042J/18.062J
    “· = O(·)” defines a relation

    Asymptotic
    Don’t write O(g) = f.
    Otherwise: x = O(x), so O(x) = x.
    But 2x = O(x), so
    Blunders therefore
    2x = O(x) = x,
    2x = x.
    Nonsense!
    Albert R Meyer, April 10, 2013 Ohblunder.1 Albert R Meyer, April 10, 2013 Ohblunder.2

    Big Oh Mistakes Big Oh Mistakes


    n
    Lower bound blunder: False Lemma: ∑ i = O(n)
    “f is at least O(n2)” i=1

    Of course really:
    should say n

    ∑ i = Θ(n2
    )
    n2 = O(f) i=1

    Albert R Meyer, April 10, 2013 Ohblunder.3 Albert R Meyer, April 10, 2013 Ohblunder.4

    1
    Big Oh Mistakes
    n
    False Lemma:
    ∑ i = O(n)
    false proof: i=1
    0 = O(1), 1 = O(1), 2 = O(1),…
    So each i = O(1). So
    n

    ∑ i = O(1) + O(1) ++ O(1)


    i=1
    = n· O(1) = O(n).
    Albert R Meyer, April 10, 2013 Ohblunder.5

    2
    MIT OpenCourseWare
    http://ocw.mit.edu

    6.042J / 18.062J Mathematics for Computer Science


    Spring 2015

    For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.

    You might also like