What would be the time complexity of halving an array and finding an element.

Is it O(n) or O(log n)?

CodePudding user response：

The complexity of dividing an (unsorted) array into 2 sorted partitions is O(NlogN).

Once you have two sorted partitions, it is O(1) to find the smallest element in either ... and hence both partitions.

(The smallest element of a sorted partition is the first one.)

CodePudding user response：

Time Complexity for Partitioned Array

If an array A is already divided in two sorted partitions P1 and P2, where P1 is distributed along the indexes of A 0 <= i < k and P2 along the indexes k <= i < n with k an arbitrary index within the range 0 <= k < n.

Then, you know that the smallest element of both partitions is their first. Accessing both partition's first element has a time complexity of O(1) and comparing the two smallest values retrieved has again a time complexity of O(1).

So, the overall complexity of finding the minimum value in an array divided into two sorted partitions is O(1).

Time Complexity for Array to Partition

Instead, if the given array A has to be sorted in two sorted partitions (because this is a requirement) and then you need to find its minimum element. Then you need to divide your array into two partitions with an arbitrary index k, sort the two partitions with the most efficient sorting algorithm, which has complexity O(n log n), and then applying the same logic exposed above in finding the minimum element.

For any given value of k, with k 0 <= k < n, we would have to apply the sorting algorithm twice (on both partitions). However, since the additive property of Complexity Computation states that the addition of two complexities of the same order is still equal to the same complexity, then for example for k = n/2 we would have that: O(n/2 log n/2) O(n/2 log n/2) still produces O(n log n). More in general O(k log k) O((n-k) log (n-k)) with 0 <= k < n and n => ∞, which will still give us O(n log n) due to the constant factors property. Finally, we need to account to this complexity the constant complexity, O(1) of finding the minimum element among the two partitions, which will still give us O(n log n).

In conclusion, the overall complexity for dividing an array A in two partitions P1 and P2 and finding the minimum element overall is O(n log n).