BigO bound on some pseudocode

Question

AllDistinct(a1 , . . . , an )
if (n = 1)
return True
for i := n down to 2
   begin
   if (LinearSearch(a1 , . . . , ai−1 ; ai ) != 0)
     return False
   end
return True

Give a big-O bound on the running time of AllDistinct. For full credit, you must show work or briefly explain your answer.

So the actual answer for this according to the solution for this problem is O(n^2). However, since BigO is the worst case running time, could I have answered O(n^100000) and gotten away with it? Theres no way they can take points off for that since its technically the correct answer right? Although the more useful O(n^2) is obvious in this algorithm, I ask because we might have a more difficult algorithm on the upcoming exam, and incase I cant figure out the 'tight' bound, I could make up some extremely large value and it should still be correct, right?

Answer 1

Yes, if a function is in O(n^2), it is also in O(n^1000).

Whether you'll get full (or any) credit for answering this way depends on the person grading your exam of course, so I can't tell you that (probably not though). But yes, it is technically correct.

If you do decide to go this way though, you should probably chose something like O(n^n) or O(Ackermann(n)), since for example exponential functions are not in O(n^1000).

Another problem is that you will probably be asked to proof the bound as well. This will be hard to do if you don't actually know the running time of the function. "n^n is really large, so the running time will probably be less than that" is not a proof. Though on the upside if you manage to correctly proof that the function is in O(n^n), you'll probably get at least partial credit.

Answer 2

That would be a trivial answer to the question. Although correct, it tells you nothing and is thus worthless. It's not about right or wrong, it's about bad and good. The better your answer, the more points you'll get for it. The question does not say you'll get credit for a terrible bad bound. Bad answers give bad marks?

(Asking for Big Theta would be a harder question. I would play nice :)