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.
I guess that the real question is what it this fabulous program doing a full minute to run on input data of size 0? :-)
ReplyDeleteto make it more realistic, do the calculation in milliseconds instead of minutes...
ReplyDeletethanks
ReplyDeleteI 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.
ReplyDelete