3 ms·
The parent poster was making a joke. A simple such method is to scan the entire list, take the largest item, remove it from the list (or give it a fake value).
by archgoon 15y ago
The parent poster was making a joke. A simple such method is to scan the entire list, take the largest item, remove it from the list (or give it a fake value). Do this k times. k is fixed, so it's O(k*O(n))=O(n).
Obviously, as k approaches n, this algorithm is in reality O(n^2)
- veyron 15y agoI'd recommend you start from Sipser [http://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/053494728X http://www.amazon.com/Introduction-Theory-Computation-Michae...] or Papadimitriou [http://www.amazon.com/Computational-Complexity-Christos-H-Papadimitriou/dp/0201530821/ref=sr_1_1?ie=UTF8&s=books&qid=1307258726&sr=1-1 http://www.amazon.com/Computational-Complexity-Christos-H-Pa...] to learn more about complexity theory (then we can discuss why your response is nonsense)
- deleted 15y ago[deleted]