Time complexity analysis for finding the maximum element

Question

I've encountered a homework problem:

which of these is an asymptotically tight upper bound for the best-case running time of an optimal algorithm that finds the maximum element in an arbitrary array of integers of size n

1. O(log n)
2. O(n²)
3. O(n)
4. O(1)
5. O(n log n)

Based on my understanding, it's O(n) since even it's the best-case we still need to scan over the arr to get the result. Please correct me

Solution 1

Yes, that's correct. One way to see this is via an adversarial argument. Suppose that you have an algorithm that allegedly finds the maximum value in the array, but doesn't inspect every array element at least once.

Suppose I run your algorithm on some array A₁ that consists of nothing but the number 0. Since your algorithm doesn't look at all positions in the array, there's some position it doesn't look at; call that position k. Now, define A₂ to be an array that's the same as array A₁, except that the element at position k in A₂ is defined to be 1.

Now, what happens if I run your algorithm on A₂? Since your algorithm never looked at position k in A₁ and A₂ is identical to A₂ except at position k, your algorithm can't tell A₁ and A₂ apart. Therefore, whatever it says for A₁ must be the same as what it says for A₂.

That's a problem, though. If your algorithm says that the maximum value is 0, then it's wrong for A₂, whose max is 1. If your algorithm says that the maximum value is 1, then it's wrong for A₁, whose max is 0. Therefore, the algorithm has to be wrong in at least one case, so it can't be a correct algorithm for finding the maximum value.

This argument shows that any deterministic algorithm that always finds the maximum value in an array must look at all positions in that array, so the runtime must be Ω(n) to be correct.

Hope this helps!

Solution 2

O(n) is the running time if we know nothing about the data in the array. Which in your case is true. "an arbitrary array of integers of size n" implies that it could be any integer array.

O(1) is possible when the array is sorted. O(nlog n) is possible if we first use quicksort to sort the array and then select the largest item. O(n^2) is possible if we first sort the array using bubblesort and then just select the largest item.

Comments

[giuseppe]

You state: "O(nlog n) is possible if we first use quicksort to sort the array and then select the largest item. O(n^2) is possible if we first sort the array using bubblesort and then just select the largest item." Yes, every complexity upper than O(n) is possible if you apply a wrong algorithm, but this is not the complexity of finding the maximum in an unsorted array