big o - Implementing a Max algorithm that is O(1) -

big o - Implementing a Max algorithm that is O(1) -

i asked implement simple algorithm find maximum number in list 1 of import condition. algorithm should o(1). wrote this:

int max = int32.minvalue; foreach (int item in _items) { if (item.compareto(max) > 0) max = item; } homecoming max;

as pointed in comment section o(n). how can find maximum number in list algorithm o(1). because me seems have iterate arrays items find max number. possible?

after taking business relationship original question comments (and, suppose, inference on part), requirements follows:

a list-like info construction with o(1) random access o(1) insertion @ end (amortized) o(1) deletion @ end (amortized) o(1) max

the straight-forward solution (keeping track of max element on insertion) fails requirement 4 you'd need recalculate max on deletion. can adjust solve problem?

yes, can! instead of keeping track of total maximum, maintain track of maximum indices i. every time append list, add together entry list contains value new maximum. total maximum, take maximum @ lastly index. delete lastly element, remove lastly entry. , element @ index i, take entry @ index , homecoming value. long underlying info construction performs these operations in (amortized) o(1) (which, say, arraylist would), we.

big-o