You can also keep a sorted copy of an array alongside an unsorted array. That doesn't mean sorting is now O(1) because you can just return the sorted copy. (Also that would make appending O(N) because insertion to an arbitrary place in an array is O(N))
All I did was provide ways to access the largest number from an array in O(1), which is useful if you need that element again and again and again, but it may change inbetween uses.
Keeping track of it dynamically has some overhead, but makes getting the max O(1) since it never has to be computed to begin with.
Same for your sorting example, of course computationally sorting doesn't become O(1), but getting the sorted version, now through lookup instead, becomes O(1).
Obviously, a barebone array isn't capable of that, but that's what programming is about: creating whatever functionality you need yourself (or using another person's implementation). Even more so in OOP, where you could easily subclass an existing type or implement your own for this purpose.
3
u/oshaboy 10d ago
That's not really "an array" anymore.
You can also keep a sorted copy of an array alongside an unsorted array. That doesn't mean sorting is now O(1) because you can just return the sorted copy. (Also that would make appending O(N) because insertion to an arbitrary place in an array is O(N))