Big O Notation in Design Theory
baseplane.com
baseplane.com
Just a couple of days ago, I gave a ten minute presentation on computational complexity as part of a high school English assignment (sic) to my classmates who mostly had hardly any programming experience at all. I based it on Knuth's paper on The Complexity of Songs: http://www.cs.utexas.edu/users/arvindn/misc/knuth_song_compl...
My classmates told me this was the best presentation they ever attended, but that's possibly because I used many pointless gimmicks such as walking around the entire room tearing a dictionary in half to explain a binary search (giving away the halves as souvenirs), making self-deprecating remarks on how boring it is and showing a picture of a friend sleeping, starting to sing like a crack addict, etc., etc..
However, whenever I asked questions, I did get immediate answers such as "this is a logarithmic relationship." So I guess I succeeded in explaining the topic.
I need to submit a writeup on the talk, and I guess it will take me a few minutes to finish typing it out. I'm not sure how many of you will want to read an explanation of big O notation written by a high school student who can't even solve the simplest of recurrence relations, but I could upload my slides and talk transcription here if you want me to...
EDIT: Ok, here it is. I am aware of the numerous blatant technical errors I have made, so please be nice :). I've also shamelessly stolen stuff from 4 or 5 places, but all those were meant for people familiar with the subject matter.
Transcription: http://www.scribd.com/doc/7539835/The-Complexity-of-Songs
Slides: http://www.slideshare.net/guestacae495/the-complexity-of-son...
> "if you want me to..." Those who want to read it will, those who don't wont. There's no shame in posting a high-school report, and you don't need to ask permission, IMO :)
As an aside: I did some work on image compression in high school, and I only wish I had had access to a group like this then, to get some quality review. Now I sound old..
Look up all the common data structures -- arrays, linked lists, hash tables, vectors, heaps, trees of various sorts, etc -- and chart out the big-oh for the operations they support. You should probably also be familiar with amortized analysis, which is what people mean when they say that hashtables or vectors have O(1) insert.
The Javadoc for java.util has interesting details on concrete implementations of these concepts; see TreeMap for example.