Q:

Knapsack Algorithm and Convex Hull

I am taking algorithm analysis course and I have algorithm homework in the java. I wrote the program and it works very well. However my teacher wanted to report about compare with the worst-case asympotic result for extra point. What does it mean? How can I compare? First one is convex hull algorithm and the second one is knapsack algorithm. My convex hull`s complexity n^3 it has worst case. Why did he want to worst case? My knapsack algorithm complexity is (n*2^n). Can you help me?

A:

You are asked to compare the asymptotic complexity of the algorithms and substantiate it with some data. This should give you some overview on the connection between the complexity and actual run-time.
They ask for worst case because, usually, that's the guarantee you can offer for the solution you have. For example you knapsack might work instantly for n=1000 if the algorithm stumbles over the solution on the first try, but you can't promise it will work for any input of that size (takes way too long).
Now, you already have the complexity, so O(n^3) < O(n2^n) so the hull is faster when you compare the complexity. Now take examples with n = 1,2,3,4,5, 10, 20, 25, 30, 50, 100, 500, 1000 and time your solutions. You will likely see that for small values of n the timings are about the same and they don't behave according to the complexity, but as n grows O(n^3) finishes in some reasonable time, while O(n2^n) will take too long (stop it after a few minutes). Plot your results and compare it with how x^3 and x2^x functions look like.

