79 ms·

Gauss turned a O(n^2) problem into O(1)

• tshaddox 6y ago
  The naive version is just O(n), right?
  • firethief 6y ago
    Addition is O(log n), so the naive version is O(n log n). Gauss would have used a pre-[1960](https://en.wikipedia.org/wiki/Karatsuba_algorithm https://en.wikipedia.org/wiki/Karatsuba_algorithm) multiplication algorithm, with complexity at best O((log n) ^ 2). Using an algorithm discovered in 2019 (cf. Harvey and van der Hoeven), it's possible to multiply in O(log n * log log n), if you have a lot of time. This is presumably optimal.
    • tshaddox 6y ago
      Sure, or you just define the input (the n) to be the number of digits in (the logarithm of) the number you’re summing up to. That’s generally how people talk about big O notation when it comes to basic arithmetic operations, mostly because we’re usually talking about computers with constant-time instructions for basic arithmetic operations (granted, only up to the maximum integer or float supported by the software).