Say you're working on a very large dataset that can't fit on a single machine (aka actual big data). What is the largest x in your O(x) algorithm that would be reasonably usable in this kind of scenario? O(N**2) is obviously out, but how would O(N log N) or O(N) fare?

  • Sharing your research helps everyone. Tell us what you've tried and why it didn't meet your needs. This demonstrates that you've taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see How to Ask – gnat Jul 29 at 13:35
  • 3
    This depends on what N measures, how large N really can get in reality, what constant factor the function f(N) in O(f(N)) has for making it an estimation for the running time, and what "acceptable" means. Or in other words: one hair on my head is too few, one hair in my soup is too many. – Doc Brown Jul 29 at 13:41
  • 2
    Asking about the limitations of a machine whose capabilties you haven't even bothered to define, is an inherently unanswerable question. – Flater Jul 29 at 13:56

The actual performance of an algorithm depends not only on the big-O factor but also on the size of N and the the constant factor.

Lets say you have a billion records and you need to perform a O(N) operation on all records. If each operation takes one nanosecond, then the whole process takes one second. But if each operation takes one second, the whole process will take 30 years. What is acceptable obviously depends on your requirements, but the example show that you can't really evaluate the performance of an algorithm solely on the basis of the big-O complexity.

| improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.