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...