BigO bound on some pseudocode_问答_开发者_运维开发者技术经验分享

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 brieﬂy 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 corre开发者_高级运维ct 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.

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

No.

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

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 brieﬂy 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.

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.

I was a prof. Profs make up exam questions, and those can have bugs. It's embarrasing when you have to throw out a question because it's got a bug and people can give trivial answers. In this case the bug is "a big-O bound". Making exam questions is tricky, because you don't want to err on the side of saying too much, like some kind of airtight lawyer statement, because that will confuse people even more.

After all, the reason for doing this is, hopefully, you'll learn something useful. If you see an ambiguous question like this, the prof will appreciate it if you say something like "I assume you mean a good big-O bound."