FOR WORST CASE: Consider decreasing order sequence say {5,4,3,2,1}
We have 5 as the Starting node..
Then we insert 4 (No of comparisons required to insert 4 in linked list = 1)
Then we insert 3 (No of comparisons required to insert 3 in linked list = 2)
and then we add 2,1 in that order and comparisons required for inserting are 3 and 4 respectively.
So total comparisons done is (for 5 keys): 1 + 2 + 3 + 4 = 10
Similarly, for n keys we have
1 + 2 + 3 + 4 + 5 + ................... N-1
Which equals to N(N-1) / 2
So, complexity is O($n^2$)