DEV Community


Discussion on: Scala Daily Coding Problem #002

detunized profile image
Dmitry Yakimenko • Edited

What you're missing in your solution is the O(n) analysis. All of your solutions except the one with the division are O(n2). The shorter solution with Scala also puts a lot of pressure on the garbage collector, as it would create a lot of temporaries. That would be another type of analysis you could make on the solution. Shorter code doesn't always mean better. In this case it probably gets an order of magnitude slower because of the temporary arrays. It's not possible to observe this with such a small test example, but if you'd make the input, let's say, 10000 elements (ignoring the fact, that the multiplication would overflow), the O(n2) would take potentially hours to finish.

I see someone already suggested a O(n) (linear) solution to this problem. If you did this analysis as a part of the exercise, maybe you'd start thinking of a faster solution yourself. In reality O(n2) is too slow for any reasonable n. In many cases O(n2) is not considered practical.

I suggest that with your next exercise to reason about the time and memory complexity as well, not just the code for the algorithm.