Maximum Number In List
You have a list a = [ a [ 0 ] , a [ 1 ] , … , a [ n − 1 ] ] , and you want to find the maximum number in the list. You come up with the following convoluted algorithm:
- Compare each pair of consecutive elements in the list, and keep track of the index of the smaller of the two.
- After going through the entire list, delete all of the elements which were the smallest (or equally smallest) in a pair. (You can assume that this step takes no additional computation.)
- Repeat the process on the new list until only 1 element remains: this must be the largest element!
Of course, this algorithm has a best-case runtime of O ( n ) ; for example, if the list were sorted, we would succeed in just one iteration with n − 1 comparisons! What is the worst-case runtime of this algorithm?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
3 solutions
It certainly seems that way -- that's why I referred to it as "a convoluted algorithm". We could instead go through the list once and keep track of the maximum value, and we'd be done with just 1 iteration!
However, we get the somewhat surprising answer that the asymptotic worst-case runtime is O ( n ) , just like the algorithms you're thinking of as "more efficient"!
Log in to reply
Now I got it.
Case 1 (Best)
1 2 3 4 5 6 7 8
2 4 6 8
4 8
8
Case 2 (Bad)
1 8 2 7 3 6 4 5
8 7 6 5
8 6
8
After each iteration, the size of the list will be halved, no matter what the arrangement is. Hence, for a set of n elements, the number of iterations = n/2 + n/4 + .... = O(n)
Log in to reply
Exactly! Except when you said "number of iterations" I think you mean "number of comparisons", which should be worst case ≈ n + 2 n + 4 n + … = 2 n = O ( n ) .
No matter how the elements in the list are arranged, the algorithm always starts with n elements and ends with 1 element. This means the algorithm always deletes n − 1 elements, i.e. makes n − 1 comparisons, so the worst-case runtime is the same as the best-case runtime: O ( n ) □
This is not exactly correct. Try to adapt your analysis to look at the number of comparisons made at each iteration.
Hint: What happens (at worst) to the size of the list after each iteration?
Log in to reply
I had initially misread the question. Now I see it. The best case is the one where the list is sorted. The following are the worst cases:
1
1 2
2 1 3
1 4 2 3
1 5 2 3 4
1 6 2 4 3 5
7 1 5 2 6 3 4
1 8 2 6 3 7 4 5
At best, the size of the list can reduce to 1 after each iteration.
At worst, the size can reduce from
n
to
⌈
2
n
⌉
. So the worst case runtime is
(
n
−
1
)
+
(
⌈
2
n
⌉
−
1
)
+
(
⌈
4
n
⌉
−
1
)
+
(
⌈
8
n
⌉
−
1
)
+
…
≈
2
n
=
O
(
n
)
When an element is kept track of, call it marked. Thus between two consecutive elements, mark the smaller one.
Note that any marked element can only be marked at most twice, since it belongs to (at most) two pairs of consecutive elements. There are n − 1 pairs of consecutive elements, and each of them marks one number. Thus we need to have at least ⌈ 2 n − 1 ⌉ marked elements. Thus after one iteration, the length of the list reduces by at least 2 n − 1 .
Let the running time on n elements be T ( n ) . It's fairly obvious that T is nondecreasing. Thus we have T ( n ) ≤ T ( 2 n + 1 ) + O ( n ) for big enough n . This gives T ( n ) = O ( n ) . It's trivial that T ( n ) = Ω ( n ) as well, since the algorithm must at least read the input, taking Ω ( n ) time. Thus T ( n ) = Θ ( n ) .
Isn't it an ineffecient algorithm to find the maximum?