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?
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.