Time complexity analysis to find the maximum element
I ran into a homework problem:
which one is an asymptotically dense upper bound for the best-case optimal algorithm that finds the maximum element in an arbitrary array of integers of size
n
- O (log n)
- O (n 2 )
- O (n)
- About (1)
- O (n log n)
Based on my understanding, this is O (n) as even at best we still need to scan through arr to get the result. Please correct me
source to share
Yes, that's right. One way to see this is through an adversarial argument. Suppose you have an algorithm that supposedly finds the maximum value in an array, but does not check every element of the array at least once.
Suppose I run your algorithm on some array A 1, which consists of nothing but the number 0. Since your algorithm does not look at all positions in the array, do not look at some position there; name this position k. Now define A 2 as an array, same as array A 1except that the element at position k in 2 defined 1.
Now what happens if I run your algorithm on A 2? Since your algorithm has never looked at position k in 1and A 2 identical to A 2except for position k, your algorithm cannot tell A 1 and A 2... So everything he says for A 1, should be the same as for A 2...
This is problem. If your algorithm says the maximum value is 0, then this is not true for A 2whose maximum is 1. If your algorithm says the maximum is 1, then this is not true for A 1whose max is 0. Therefore, the algorithm must be wrong in at least one case, so it cannot be the correct algorithm for finding the maximum value.
This argument indicates that any deterministic algorithm that always finds the maximum value in an array must look at all positions in that array, so the execution time must be correct. & Omega; (n).
Hope this helps!
source to share
O (n) is runtime if we don't know anything about the data in the array. Which is correct in your case. "arbitrary array of integers of size n" means that it can be any integer array.
O (1) is possible when sorting an array. O (nlog n) is possible if we use quicksort to sort the array first and then select the largest element. O (n ^ 2) is possible if we first sort the array with bubblesort and then just select the largest element.
source to share