Is it sometimes better to write solution in O(n^2) than in O(n)?

Question

If we have solution to problem something like this:

public void solutionLinear(Problem problem) {
  for (int i = 0; i < problem.getSize(); i++) {
     // do something with problem and compute solution
  }
}

...and if we have solution to problem which is like this

public void solutionQuadric(Problem problem) {
  for (int i = 0; i < problem.getSize(); i++) {
    for (int j = 0; j < problem.getSize(); j++) {
      // do something with problem and compute solution
    }
  }
}

Is it better to write second solution sometimes and when?

Answer 1

Big O complexity measurements omit constant coefficients, so "O(N) complexity" and "O(N^2) complexity" roughly correspond to "runs in A*N + B seconds" and "runs in C*N^2 + D*N + E seconds" respectively. The latter may be preferable if A & B are large and C & D & E are small.

Consider the code samples:

public void solutionLinear(Problem problem) {
  for (int i = 0; i < problem.getSize(); i++) {
     do_stuff_taking_one_hour();
  }
}

public void solutionQuadric(Problem problem) {
  for (int i = 0; i < problem.getSize(); i++) {
    for (int j = 0; j < problem.getSize(); j++) {
      do_stuff_taking_one_second();
    }
  }
}

Despite being O(N^2), the latter algorithm will run faster as long as problem.getSize() is less than 60.

Answer 2

The other answers do a good job of explaining the situation where a O(n^2) solution is actually faster than a O(n) solution, so I will be focusing on the other side of the question, namely, "Should you favor readability over performance?"

Short Answer: No

Long Answer: Generally no. There are times when the difference in performance is small enough that the gains you get from readability might be worth it. For example, people debate over the relative speed of switches and if/else statements, but the difference in performance is so small that you should really just use whichever is more maintainable for you and your team.

Outside of those cases, the potential for slowing down your program generally outweighs the gain you get from the code being readable. If it is well written code and the only problem is that the algorithm is more complex, you can solve that problem by leaving documentation for the next person to work on it.

I think a good example of this trade-off is bubble-sort vs quick-sort. Bubble-sort is a very easy algorithm to understand and is very readable. Quick-sort on the other hand is far less intuitive and definitely harder to read. However, it would not be appropriate to replace quick-sort with bubble-sort in production code because the performance difference is too extreme. The situation you asked about is even worse than that because you are talking about O(n) vs O(n^2) whereas bubble-sort vs quick-sort is O(n) vs O(log(n)) (in the best case of course).

Answer 3

When It Comes to Speed

When it comes to runtime in particular, what generally everyone else is saying is right; there usually is a hidden constant whenever you refer to a function in Big O. If the function with the O(n^2) had a relatively small constant and didn't run particularly long, it could be faster than a function which ran O(n) with a large constant and ran longer.

---

Don't Forget About Memory

Runtime isn't the only thing to consider when writing or using an algorithm; you also need to worry about the space complexity. If you happened to need to conserve memory in your application and you had to choose between a function which ran in O(n) but uses a ton of memory and a function which ran in O(n^2) but uses much less memory, you might want to consider that slower algorithm.

A good example for this is quicksort vs. mergesort - in general, mergesort is consistently faster than quicksort, however quicksort is done in place and doesn't require allocating memory, unlike mergesort.

---

In Conclusion

Is it sometimes better to write solution in O(n^2) than in O(n)?

Yes, considering the specific circumstances of your application, the slower option may indeed be the better one. You should never rule out an algorithm simply because its slower!