An esoteric lossy algorithm has this time complexity because it simply “drops” each element of the input array that is less than its predecessor. For 10 points each:
[10m] Name this time complexity of an algorithm that accesses each element in an input array exactly once. You can give your answer in big O notation.
ANSWER: big O of n [or linear time]
[10e] That esoteric algorithm performs this task of ordering the values in an array that is typically performed with time complexity “big O of n log n.”
ANSWER: sorting [accept dropsort] (The esoteric algorithm is dropsort.)
[10h] This non-comparative sorting algorithm can run in near-linear time when sorting small integers. This algorithm iteratively puts elements into buckets based on a stable sort of their values in successive digits.
ANSWER: radix sort [prompt on bucket sort or digital sort]
<Michael Bentley, Science - Computer Science> ~21133~ <Editor: David Bass>