Question about problem 12.1, variant 2

#1

I find it hard to find the maximum in a non-strictly-ascending-then-non-strictly-descending array in less than O(n) time, in particular, when all elements are equal. Do you have any solution or hints for solving this problem?

I could find the maximum in a array which is strictly-ascending-then-non-strictly-descending in O(logn) by checking whether the middle point is on the ascending or descending subarray. However, for the non-strictly ascending and descending one (i.e. with duplicates), I could not find any easy way to check this. (I googled for a while but all solutions are only for strictly-ascending/descending arrays).

0 Likes
#2

you are correct, it’s not possible to find the maximum in a non-strictly-ascending-then-non-strictly-descending array in sublinear time. your reasoning is on target, the worst-case arises when all elements are equals.

somewhat more formally, as an adversary, i can force you to examine all entries in the array. basically, if you examine fewer than n entries (n is array length), i return 0 each time, and you will not know if the max is 0 or 1 (since i can set the unexamined entries to either without violating the constraint).

the moral of the story is that the presence of duplicates can make life tough. we saw this also, e.g., in the find min in a cyclically sorted array.

that’s not to say the property is not helpful in practice, since it can often let you prune our parts of the space. however, complexity is always measured on worst-case inputs.

bye,
adnan

0 Likes