Thursday, October 6, 2011

How not to teach runtime analysis

The design and analysis of algorithms is my area of specialty: I know it like the back of my hand, and do not need to prepare for a freshman level class on running time. I can always improvise examples to illustrate my points. Or so I thought.

Here is a question I asked in class.

Suppose you have a program that, on data of size n, takes one minute to complete. How long would it take on data of size 10n, if the runtime is:
a) T(n)= n (linear)
b) T(n)=n^2 (quadratic)
c) T(n)=2^n (exponential)

Here are the answers I got.

a) T(10n)=10n = 10 T(n) so it would take ten times as long: 10 minutes.
b) T(10n)=100n^2 = 100 T(n) so it would take one hundred times as long: 1 hour and 40 minutes.
c) T(10n)= 2^{10n}= (T(n))^{10} so it would take time 1^{10}, which equals one: 1 minute.

So much for my pedagogical presentation of the growth rate of functions.


  1. I guess that the real question is what it this fabulous program doing a full minute to run on input data of size 0? :-)

  2. to make it more realistic, do the calculation in milliseconds instead of minutes...

  3. I like your post but I want to tell you that I am very bad when it come algorithms. I don't understand the logic behind these algorithms. If there is any easy methods to understand algorithms then please explain that method. So I don't have answer for your question. Thanks.


Note: Only a member of this blog may post a comment.