addressalign-toparrow-leftarrow-rightbackbellblockcalendarcameraccwcheckchevron-downchevron-leftchevron-rightchevron-small-downchevron-small-leftchevron-small-rightchevron-small-upchevron-upcircle-with-checkcircle-with-crosscircle-with-pluscontroller-playcrossdots-three-verticaleditemptyheartexporteye-with-lineeyefacebookfolderfullheartglobegmailgooglegroupshelp-with-circleimageimagesinstagramFill 1linklocation-pinm-swarmSearchmailmessagesminusmoremuplabelShape 3 + Rectangle 1ShapeoutlookpersonJoin Group on CardStartprice-ribbonprintShapeShapeShapeShapeImported LayersImported LayersImported Layersshieldstartickettrashtriangle-downtriangle-uptwitteruserwarningyahoo

Talk about the Big-O

Abstract:

What is Big Oh notation, what problem does it attempt to solve, and how does it work?

There are many kinds of performance problems.  Some are very implementation-specific, like slow runtimes, needlessly synchronous operations, or sub-optimal register allocation.  There are also differences between algorithms which are (largely) independent of implementation details.  When we wish to focus on implementation-independent performance differences of two algorithms, we use a family of notations including "Big Oh" to describe the "asymptotic" behaviour of the function -- that is, the behaviour "in the limit".

This talk will review the conceptual motivation for asymptotic analysis, walk through the definition of Big Oh notation, and look at applying it to some simple algorithms as implemented in Python.  Hopefully the difficulty level will be suitable for an undergraduate course on algorithm design.


Bio:

Jeremy Holman thinks that algorithm puzzles make a fun pastime, but are overrated as an interview technique.  He finds it easier to think about tricky problems without the distractions of undue ceremony, which is one of the reasons he prefers Python.


*This is a Bay Area Python Interest Group (BayPIGgies) organized event. Please also see their web page: http://baypiggies.net/ 

Join or login to comment.

  • Marty F.

    Hey all! As I brushed up on the more common instances of time-complexity analysis today, I stumbled upon a handy quick-reference: http://bigocheatsheet.com/ There are also lots of helpful links in the comments.

    1 · December 11, 2013

  • James N.

    The video from this talk can be viewed at: http://youtu.be/1xCSqMbxd_k

    Also, please subscribe to our Bay Piggies channel on YouTube! If we get 100 subscribers, Google will allow us to live stream.

    Happy holidays everyone!

    Cheers,
    James

    1 · November 30, 2013

    • Glen J.

      Cool! Can you tell us what equipment we would need to live stream. I know many who would be interested (and could get subscriptions) if we have a plan to get to live streaming.

      December 5, 2013

  • James N.

    Ill be filming this talk and posting to the bay piggies youtube channel. To subscribe to the channel, search for "bay piggies" in the "browse channels" area on youtube or find a link to last month's talk in the "Good Enough is good enough!" post on my site: nicholsonjf.com

    November 21, 2013

    • James N.

      I'm trying to upload with a higher resolution this time, but no promises. Our camera is old :( The video should be up tonight.

      November 30, 2013

    • James N.

      I was able to get it up to 360p this time. That's "good enough" right?!

      November 30, 2013

  • Kim

    I'm sad I missed it.

    November 25, 2013

  • Peter

    Hello,

    first time visiting - really like the group.
    A source I found is:
    https://www.udacity.com/course/cs215

    It's mostly about graphs, but they use Python for their programming exercises. They claim it is an intermediate class. Yes, they talk about Big-O

    November 22, 2013

  • Bibin Thomas K

    Great talk
    This is truly a hard topic to cover in a short duration.
    I love the effort to make people aware of algorithmic analysis and its value. Here is a link for those who are interested in diving deeper.
    http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/

    The video lectures here talk about various algorithms and their analysis.

    The reason I value this particular class is because all of the examples and class projects use Python code.

    November 22, 2013

  • Brian S.

    "Python Algorithms" book, http://amzn.to/1frDWbg, is a similarly entertaining take on a normally dry topic.

    1 · November 22, 2013

  • A former member
    A former member

    I don't know if it was me but I was not at all impressed with today's presentation. It was dull and unimpressive.

    1 · November 21, 2013

    • Utkarsh S.

      I don't agree. 1hr is very short time to explain big-oh. Jeremy was pretty good at what he explained.

      November 22, 2013

  • A former member
    A former member

    I agree. Normal usage of "Oh of (n) " connotes an upper bound on algorithms, and I've forgotten the formal definitions. It brought back memories of trying to find t and M in algorithms class - and how hard it was. I'm also impressed by the speaker's attempt to open these concepts to programmers who are not formally trained. I think that all of the key points of a solid presentation were there, but that it's delivery could be smoothed out with more examples and perhaps visualizations. This was my first Meetup with the Python group after trying for the last several months to make it, and I was happy that I came. I met some cool people and was reminded of important core concepts. I was REALLY impressed by Random Access. What a great way to look for jobs and employees!

    November 22, 2013

  • A former member
    A former member

    I am glad I attended. I walked out with a better understanding of Big Oh than what I still recall from my CS degree, and more importantly, a practical understanding of when to use it in my job and how. I liked the speaker's demeanor and humor as well. I think some demos of working Python code showing behaviors of algorithms in real-time, and the way the timing behaves relative to input, would have played better with this crowd.

    November 22, 2013

  • Glen J.

    I especially liked the beginning of the talk - the introduction by walking through Python code. I would also have liked an intuitive introduction (several superimposed graphs) of the common O()-notations so we could see where we were going by the end of the talk -- that would probably have been more helpful than reviewing mathematical definitions.

    I liked the speaker's demeanor in the introduction and his use of humor. I also liked that his motivation was to genuinely help programmers that may not have had a CS degree or have seen O() notation before.

    1 · November 22, 2013

  • Han K.

    What's the parking situation like over there?

    November 21, 2013

    • James N.

      I've never had a hard time either you should be fine

      November 21, 2013

    • Han K.

      Alright, thank you guys.

      November 21, 2013

  • Ahmer K.

    I'll be unable to attend tonight. :(

    November 21, 2013

  • Dan B.

    I just wrote up a tech-tip on using LibSVM and Postgres to backtest machine learning ability to predict the stock market. The tip makes use of a bit of Python: http://bikle.com/techtips/libsvm#libsvm

    November 16, 2013

  • Marty F.

    This actually came up the other day... I'm eager for the refresher! :-D

    November 14, 2013

  • Tim T.

    I love the phrase "distractions of undue ceremony".

    November 14, 2013

  • sukhee s.

    Look forward to coming to my first event

    October 27, 2013

Our Sponsors

People in this
Meetup are also in:

Sign up

Meetup members, Log in

By clicking "Sign up" or "Sign up using Facebook", you confirm that you accept our Terms of Service & Privacy Policy