Someone sent me an email the other day looking for information to help him understand Big O notation. Big O notation is used to compare the efficiency of algorithms. If you teach Advanced Placement Computer Science (APCS) then this is something you have to teach because it appears all over the exam. If you are a professional developer or computer scientist than you’d better understand it as well. In real life it is part of the vocabulary that lets people have some important discussions about what algorithm to use.
I had some materials that I’ve used in the past that I send to my correspondent but the web links for the original locations were no longer valid. I don’t like the idea of trying to archive other people’s work. I’d much rather provide links so that people can go to the source. So I asked a number of my teacher friends what online links they were using. What follows are the links they sent me. As always with Internet links I can not be sure they will stay valid for ever. But as of this morning these were all working links. I hope that others find these useful.
http://en.wikipedia.org/wiki/Big_O_notation – it seems like you can’t discuss anything computer related without a link to the Wikipedia article
http://www.cprogramming.com/tutorial/computersciencetheory/algorithmicefficiency1.html – Algorithmic Efficiency — Beating a Dead Horse Faster – This is a short but interesting introduction to Big O notation.
http://www.cs.wisc.edu/~hasti/cs367-common/notes/COMPLEXITY.html – Complexity and Big-O Notation – Some rather complete notes from a course at the university of Wisconsin
http://www.cs.duke.edu/csed/talks/sigcse2004/bigo/slides.ppt – Tradeoffs, intuition analysis, understanding big-Oh aka O-notation – a PowerPoint presentation by Owen Astrachan of Duke University. Very well done.
http://staff.fcps.net/jlreed/CS2Files/11.2%20Compl… – 11.2 Complexity Analysis A PowerPoint presentation apparently by J L Reed. Used by several other teachers that I know of.
One of these days I’ll have to write my own notes up. I’ve never been all that strong on understanding and teaching Big O (my students already know that I don’t know everything so that mystery is gone) so I really need to spend some time working on this. My feeling is that working on it hard enough to explain it well will force me to a much higher level of understanding. That’s usually how things work.