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

No.

It might be all clever and HA! I got you! but that's not the idea. (and you know that)

Answer 2

At a guess, you'd probably have to talk to the professor, and argue with him a bit to even get partial credit for an answer like that. Depending on how much he values theory vs. practicality, he might give you partial credit, or he might give no credit -- but I can hardly imagine a professor who'd give any credit without your explicitly pointing out how it's (semi-)correct, and some might not even then.

Answer 3

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 4

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 :)

Answer 5

If the professor ask you for BigO of it you can answer whatever BigO you think but you must prove it as it say For full credit, you must show work or briefly explain your answer.

BigO is not useless. For problems it's easy to get Upper Bound (BigO) graeter; e.g.
Sorting problem: you have the simple bubble sort and you can proof that is n^2 (right?), so upper bound of Sorting problem is n^2 (because exists and algorithm that solve it in that time, but if you go on with maths, you see that the problem has a lower bound of log(n!) ). So n^2 was a good answer until you proof it's log(n!). There are many problems that we know just BigO but not the lower bound, so it's not useless.

If you can say that a program halts you can always compute is BigO with some math, but is not always easy (exists even ammortized complexity) but it's simpler than problems lowerBound. So BigO is not so important in algorithm, but it's not useless.
The important thing is that you understand what it means; then if you can get any BigO of that program you can write it on that exam paper that is a function from Student to number.. and good luck.