Posted by: Gajedi January 29, 2010
Login in to Rate this Post:
0 
? 
?
O(n) is the asymptotic upper bound of algorithm, the best case is known as big Sigma(n), and the average case is known as big Theta(n). O(n) is usually considered as it represents the worst case of an algorithm. There are notation such as small o(n) and small omega(n) which are upper and lower case but are not asymptotically bounded.
In the simplest word, O(n) is the worst case running time of an algorithm.
Most of the non comparison based sorting techniques are either unstable or assume that the number of items to be sorted is much less than 2^k (k is the size of each key). Counting sort is exponential in runtime cost in worst case. The only sorting algorithm that is stable and can be implemented fairly easily is LSD radix sort, but getting n much less than 2^k is very hard. (See wikipedia)