Comment on The Dollar Redesign ProjectparentComments−wooster17yWith different sized bills:* Sorting is O(N) [see spaghetti sort: http://en.wikipedia.org/wiki/Spaghetti_sort]* Retrieval is O(1).Further, retrieval is O(1) even in unordered sets, so sorting is irrelevant.(Also, how is sorting on insertion O(log(N))? For each new bill, finding the correct spot is log(N), so you're still looking at O(N log(N)).)−sp33217yI only meant for inserting one bill, so N is the number of bills you have already. Using a binary search on a sorted list, either to find a specific denomination you want or to find the correct spot for a new bill, is O(log(N)).
Comments
With different sized bills:
* Sorting is O(N) [see spaghetti sort: http://en.wikipedia.org/wiki/Spaghetti_sort]
* Retrieval is O(1).
Further, retrieval is O(1) even in unordered sets, so sorting is irrelevant.
(Also, how is sorting on insertion O(log(N))? For each new bill, finding the correct spot is log(N), so you're still looking at O(N log(N)).)
I only meant for inserting one bill, so N is the number of bills you have already. Using a binary search on a sorted list, either to find a specific denomination you want or to find the correct spot for a new bill, is O(log(N)).