Complexity Based Efficiency Tests

[felipesantoz]

It's a common coding challenge to be given an upper bound on the time complexity of a solution. A classic example is to write a sorting algorithm which runs in time O(nlogn), to which an implementation of merge sort is a valid solution, but of insertion sort is invalid, as it runs in time O(n^2). However, I've yet to come across this type of problem on Codewars.

It is of course undecidable to check the time complexity of an algorithm, but there are empirical means of testing it with a negligible probability for error. So, I wanted to discuss this. Do these types of problems already exist on Codewars and I just missed them? If they don't yet exist, why not?

[Blind4Basics]

Looks like you missed them: search for performance tags.

[Madjosz]

Never say "never" though: Specialty Sort

[Blind4Basics]

"cw"... x)

[felipesantoz]

The only types of problems I can find under the performance tag are the ones like this one, where the naive algorithm has an exponential runtime, and will inevitably lead to a timeout. What I'm looking for is a problem where the naive algorithm is itself polynomially bounded (e.g. O(n^2)) and is unlikely to lead to a timeout, but there is still a more efficient algorithm (e.g. O(nlogn)), and the Kata forces you to come up with the latter. Would you be able to link me an example like that if it exists?

[Blind4Basics]

https://www.codewars.com/kata/search/my-languages?q=&tags=Performance&order_by=sort_date%20desc

[felipesantoz]

Yeah, I ran that search and couldn't find quite what I'm looking for. Maybe I'll draft up a Kata to make it more clear what I mean.