Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Big-Oh Notation for 'n00bs'

  1. Mar 8, 2009 #1
    Hello everyone,

    Im doing a relatively simple report/project in my science class (8th grade) on the efficiencies of various sorting algorithms, and I need to explain Big-O notation in a way which is:

    1) Easy for a middle aged teacher who's knowledge of a computer pretty much stops at " It uses electricity"

    and

    2) Is compact enough to be able to put onto a poster board that people don't give up on reading it and walk away.

    So what i've come up with so far is
    Any suggestions as to how I could make this better, and (even better) is anything up there wrong?
     
  2. jcsd
  3. Mar 8, 2009 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Strictly, what you wrote is wrong. An algorithm that is O(n) takes at most kn steps for some k, which is often greater than 1.

    In the context of sorting, to give your readers intuition, I would certainly explain that O(n^2) algorithms are "slow" and that O(n log n) algorithms are "fast".
     
  4. Mar 8, 2009 #3

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    What is the actual intent? I suspect it's unlikely that explaining Big-Oh notation is the best way to convey the point you're trying to make....
     
  5. Mar 8, 2009 #4
    "Big O gives the upper bound for time complexity of an algorithm."
    This is a little wordy for a general, non-technical description of big-oh notation. You may want to make it more colloquial. For instance...
    "Big O tells you how slow a certain algorithm may be in the worst case."
    "Big O notation provides a means for describing the worst-case running time of a certain computational procedure"
    etc.
    The content is good, though.


    "For example, an algorithm that is O(n) (where n is the number of items to be processed) means that the highest amount of instructions executed is equal to the number of instructions in the algorithm."
    This is misleading... the wording is good, but the "n" in O(n) has nothing to do with the number of instructions in the algorithm, but the size of the problem. It's generally true that larger problems cause more instructions to be executed. I'd phrase it a little more precisely.

    "If an algorithm is O(n^2), that would mean that the highest number of instructions executed is equal to the number of instructions in the program squared."
    See above.

    I like CRGreatHouse's idea... I would explain why an O(n lg n) algorithm will beat an O(n^2) algorithm (usually... you could provide examples where it didn't, though) and why any sorting algorithm must take at least O(n)...

    It's an interesting idea, and I think you could really make it work. Examples will be key. Include examples, if you can.
     
  6. Mar 10, 2009 #5

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Right. It would be worth mentioning that sorting algorithms* take at least O(n) time, and that algorithms take at least O(log(n!)) = O(n log n) time in the worst case.

    * Assuming they always produce correct output and accept all inputs.
     
  7. Mar 10, 2009 #6

    alxm

    User Avatar
    Science Advisor

    I would not bother with details like 'in the worst case', etc.
    What's wrong with simply saying something like:
    Saying 'number of instructions executed' is a pretty complicated way of conveying the simple idea 'amount of time'. It's also incorrect by virtue of being more specific than the actual definition, which is in terms of abstract 'steps'. Which can be assumed to be proportional to instructions, but you might as well assume it's proportional to time - which is what people are interested in anyway.
     
  8. Mar 10, 2009 #7

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    I agree that saying 'time' is probably better than 'instructions', since you need a proportionality constant either way. But I think that the worst-case distinction is important in the case of sorting, where one popular algorithm (you know the one... Hoare's QuickSort) has very different behavior on average and in the wost case.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Big-Oh Notation for 'n00bs'
  1. Big O Notation Question (Replies: 15)

  2. JQuery notation (Replies: 1)

  3. O notation (Replies: 1)

Loading...