Is this true? The naive algorithm's outer loop (i) counts n - 1, while the inner loop (j) begins at i + 1 (so counts progressively less than n - 1).
Not a CS major, is this roughly equivalent (for large values of n) to O(n2) or is it, as it appears, something less?
In the end it doesn't make a difference for big-O analysis because it's used to describe the behavior when n approaches infinity, where the quadratic factor takes over.
[Ed: I should add that it also prevents testing an object against itself.]
The algorithm is O(n^2) because every pair will be checked once.
It does not necessarily describe performance of the algorithm. `20n2^+5n` and `2n^2 + 9001n` are both O(n^2)
Not necessarily true. It does indeed describe performance of the algorithm. It just compares scenarios with coarser granularity. You can tell from the very start that a O(1) algorithm is expected to outperform a O(N²) alternative.
It is not necessarily true that an O(1) algorithm will outperform an O(n^2) alternative on a particular set of data. But it is true that an O(1) algorithm will outperform an O(n^2) alternative as the size of the input data increases.
Yes, that's the definition of asymptotic computational complexity. That's the whole point of these comparisons. It's pointless to compare algorithms when input size is in the single digit scale.
If your O(1) algorithm takes an hour for any input, and the competition is O(n) it may seem like there must be cases where you're better, and then you realise n is the size in bytes of some data in RAM, and your competitors can do 4GB per second. You won't be competitive until we're talking about 15TB of data and then you remember you only have 64GB of RAM.
Big-O complexities are not useless, but they're a poor summary alone, about as useful as knowing the mean price of items at supermarkets. I guess this supermarket is cheaper? Or it offers more small items? Or it has no high-end items? Or something?
All that different complexity classes show is that there is some n for which one outperforms the other. In practice this n can be extremely large.
O(1) is by no means expected to outperform O(N^2) for any practical dataset. One algorithm is constant time (even though the constant can be so large that it will not finish before heat death of the universe), the other gets quadratically slower as the input size increases.
For example if O(n^2) algorithm can be implemented with SIMD, you could easily expect it to heavily outperform O(n) algorithm on many practical datasets when wall-clock performance is measured.
You can't draw immediate conclusions about performance of the algorithm from Big O class alone.
SIMD is also not easy to reason about as the formula changes quite a bit once you become bottlenecked by bandwidth - Zen 5's AVX512 implementation lets you blaze through data with 128-256B/cycle (think >128B/0.25ns) which is absolutely bonkers. But that quickly comes to a halt once you exceed data in L1 and L2 - streaming data from/to RAM is just about 32B/c.
So the consideration of memory traffic becomes important, where "better by Big O classification" algorithms with more granular data access might start to outperform.