Examples

With a low amount of data, the difference between O(1) and O(n2) is negligible. For example, let’s say you have an algorithm that needs to process 2000 elements.

  • An O(1) algorithm will cost you 1 operation
  • An O(log(n)) algorithm will cost you 7 operations
  • An O(n) algorithm will cost you 2 000 operations
  • An O(n*log(n)) algorithm will cost you 14 000 operations
  • An O(n 2 ) algorithm will cost you 4 000 000 operations

The difference between O(1) and O(n2) seems a lot (4 million) but you’ll lose at max 2 ms, just the time to blink your eyes. Indeed, current processors can handle hundreds of millions of operations per second. This is why performance and optimization are not an issue in many IT projects.

As I said, it’s still important to know this concept when facing a huge number of data. If this time the algorithm needs to process 1 000 000 elements (which is not that big for a database):

  • An O(1) algorithm will cost you 1 operation
  • An O(log(n)) algorithm will cost you 14 operations
  • An O(n) algorithm will cost you 1 000 000 operations
  • An O(n*log(n)) algorithm will cost you 14 000 000 operations
  • An O(n 2 ) algorithm will cost you 1 000 000 000 000 operations

I didn’t do the math but I’d say with the O(n2) algorithm you have the time to take a coffee (even a second one!). If you put another 0 on the amount of data, you’ll have the time to take a long nap.

results matching ""

    No results matching ""