6 ms·

Well, now this show how polynomial time isn't necessarily any better than O(2^n), or exponential time in reality. Once the k grew bigger in O(n^k), our modern m

• loeg 7y ago
  O(N^2) is strictly better than O(2^N). Per the article, this algorithm fell over at 3 billion bytes of data, but wasn't especially noticeable at 300 million bytes of data.
  • saagarjha 7y ago
    Better from an theoretical perspective. Depending on n and any constant factors, one or the other may end up winning in reality.
    • loeg 7y ago
      In practice, not really either. Unless "N" isn't actually variable and is basically zero.
• read_if_gay_ 7y ago
  The point where polynomial time becomes impractical is far beyond the point where exponential becomes impractical. It's like for n=10 your smartphone can run an exponential algorithm instantly but for n=20 the fastest supercomputer on earth will take forever. Not true for polynomial.
• actuator 7y ago
  Not really. The n is huge, there is an enormous difference between an exponential complexity like O(2^n). Many algorithms are O(N^2) and are perfect for their use case. To see the difference. - 100^2 -> 10^4, 2^100 -> 10^10 - 1000^2 -> 10^6, 2^1000 -> 10^100 Look at the difference in order of growth. Just to give a very simplified comparison, your individual processor core can run about 10^9 simple instructions in a second.