Seonglae ChoLinear time for special cases
Pseudo polynomial complexity because there is k in Asymptotic Notation (because of bit transition, strictly exponantial complexity). So it has a problem when
no comparison between elements, requires we know the value set is limited and order or value set. auxiliary storage requires length of value set. Space complexity is too.
- store count for each value’s count to auxiliary storage
- change auxiliary storage to accumulated index like Fibonacci sequence
- backward, we can allocate values reducing 1 per allocate