Description
Speaker: Jeremy Holman Topic: Talk about the Big-O Date: Nov-21-2013 Location: LinkedIn, Mtn. View 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/