Issue
What would be the time complexity of partitioning an array in two and finding the minimum element overall?
Is it O(n) or O(log n)?
Solution
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.)
Answered By - Stephen C
Answer Checked By - Willingham (JavaFixing Volunteer)
