Posted on 05 February 2022, by Kevin Mora
In an unsorted array, we cannot skip an element unless we already know something about that element, making O(N) not feasible.
Knowing the data structure, whether that is a heap, tree, or if it’s ordered, will help us reach the solution in O(log(n)). On the other hand, if it's sorted, then we can locate the element in O(1), and based on the orientation, for example, of the heap, we can locate the minimum or maximum in the same time complexity.
Let’s assume we are still not convinced, and we would thus like to assume that we are able compute this in fewer than O(N) steps. Well, by applying the logical arguments we learned in our discrete math class, the first premise would indicate that we did not read all the input – now, make any of the unread input the maximum element (i.e., instances that differ from the output of our algorithm) and we have a contradiction; therefore this is not possible, at least for classical computers.
When it comes to quantum computers, Grove’s algorithm can identify an x such that P(x) holds and where P can be calculated on a quantum computer in O(1) processes. In this instance, the predicate must perform a linear search because P must be able to determine whether a given x is the minimum or maximum element of a list.
Algorithm Performance on Varied Input Sizes: It's a known fact in computer science that certain algorithms are faster on smaller inputs but slow down significantly as the size of the input increases, following complexities like O(logn), O(n), etc.
Regarding this, I have two main inquiries:
For certain ranges of input sizes, simple algorithms can be created that exhibit these special features. Since these algorithms show two separate performance phases, one that rises to a specific input size threshold and another beyond it, analytical approaches are recommended for examining these characteristics.
This brings up an important question Why do algorithms act in the way they do? One helpful analogy would be to think of an endless quantity of input. Imagine that obtaining this data for processing comes at no cost in terms of time or location, unlike a continuous stream. An algorithm of finite complexity is fundamentally defined in terms of time and space by the largest amount of data that it can process. Processing complexity would inevitably rise with each additional piece of data.
Theoretically, you might increase the space complexity of an algorithm to make it capable of handling endlessly huge inputs, but this would result in a contradiction where the input finally exceeds or exactly matches the algorithm's complexity. The algorithm's behavior changes radically at this mathematically determinable critical stage.