On the insertion sort algorithm, I wrote a typical algorithm that takes O(n^2) worst case. Initially I used Python, and it gave me a TLE when the input list is big (5000 sorted elements). Later I rewrote the exact algorithm in C++ and it was accepted.
I understand Python will be slower being interpreted language and all. But hasn't OJ taken that into consideration and scale the criteria accordingly?
Do you use any functions or containers in Python?
And I don't think, that leetcode take this difference into account.
It doesn't needed: This site is not for challenging, it is to prepare for interview.
It doesn't matter, which language you use, O(n^2) will NOT be ACCEPTED at any interview in any languages.
Of course, you can submit it in c++ and get accepted. But this it the same as use java for "implement big arithmetics" (it has standard function). You will get accepted on this site, but you will failed interview.
So there is no reason to implement different time limits for each language. Right solution never get TL.
I am confused here, the problem is to use Insertion Sort, and you said O(n^2) is not acceptable, but I thought the worst case running time for insert sort is O(n^2), maybe I am wrong.
So I am just wondering, say in an interview, the interviewer asked you to implement an Insertion Sort, but Insertion Sort is naturally O(n^2) worse time, and because O(n^2) is not acceptable in an interview, so we should just implement another O(nlogn) solution?