Posted by: Gajedi January 29, 2010
How do you sort a Linked List (singly connected) in O(n)
Login in to Rate this Post:     0       ?        
http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/6_046J-2005-L02.pdf

1987 AD, hope the above link will provide a clear understanding about some asymptotic notations. 
Read Full Discussion Thread for this article