I have a linear search algorithm with 2n 2 comparisons in the worst case. How do I prove mathematically that the number of comparisons in the worst case for linear search is in Θ(n), which I assume is big-theta?

Everything I can find on big-o and such confuses me.

Edit: Ok to be more specific. I know that I have to prove that 2n 2 is in O(n) and Ω(n), but it is actually is that I don't know how to do.

CodePudding user response：

I'm pretty sure that your problem isn't in why it is true, but rather what constitutes a proof that it is true. So I'd recommend that you read How I Do Proofs and learn how to break doing proofs into very digestible steps.

You already know that proving that f(n) is in Θ(n) requires proving O(n) and Ω(n).

Proving O(n) requires (by definition) proving that there is an N and a k such that for all n with N < n, f(n) < k*n. For that it is sufficient to give N and k and then show that the statement is true. I suggest using N = 1 and k = 4.

Similarly proving Ω(n) requires (by definition) proving that there is an N and a k (not the same as before!) such that for all n with N < n, k*n < f(n). For that it is sufficient to give N and k and then show that the statement is true. I suggest using N = 1 and k = 2.

And to "show that the statement is true" it is sufficient to do basic algebra.

The key to formal proofs is not going on on at length. It is making sure you covered every item on your checklist with no steps left out.