Posted by: yuanzhan | October 6, 2010

## Grades for HW2 and some explanations

Atri will hand out graded HW 2 in Wednesday’s lecture.  Sorry for the delay.

Before Atri returns the HW 2 to you guys, I would like to point out some common mistakes I found in the solutions of the Q2 and Q3 in HW2 :

In Q2, you are asked to argue about the growth order of different functions.

• Letting n equal to some “big” number may give you some basic hint about which function has a bigger value at that point, but you cannot use it as a proof of the growth ordering of different functions. To give a proof about the growth order, you need to show conclusion holds for all n which are “big enough”, not just one or two special big numbers.

In Q3, an algorithm is presented and you are asked to find  upper and lower bounds on its running time. The problem is a little tricky, because it does not specify how it finds the smallest number among $a_{\tt min},\dots, a_n$ in step b(i).

• If you want to sum up all running time of every step to get the total running time first, you should specify how your algorithm would implement b(i) step. For example, you may say the algorithm will do a linear scan. Most students just assume the algorithm will go like that. However, to be rigorous, you should state step b(i) clearly before you analyze it. (Putting this information in the proof idea section would be one way to go.)
• Another common mistake was in the proof of the lower bound of the algorithm. Some of you claimed that the inner loop will not stop scanning until it reaches the end, and therefore the inner loop’s running time is $\Omega(n)$. Since the outer loop runs for $n-1$ times, the total running time should be $\Omega(n\cdot (n-1))$ which is $\Omega(n^2)$.  This is not right because the inner loop’s running time is NOT always $\Omega(n)$.  Here’s a simple counterexample. When ${\tt min} = n-1$, the b(i) only takes $1$ step to find the smallest one, and obviously $1$ is not  $\Omega(n)$. The right thing to do here is to add the running times of all the iterations of the inner loop together, and then trying to prove a lower bound for it.