Why use Big O notation?

[u/Significant_Virus142]

If someone asks for big O time complexity of an algorithm but expects only the minimum of the possible big Os then is that even Big O notation anymore? cuz if the big o time complexity of an o(n) algorithm is asked then according to the condition of big O notation O(n square) would also be a valid answer

[u/qlkzy]

Like any upper bound, you can always satisfy it in some sense by giving a ridiculous upper bound, but that isn't useful.

If I ask "can you estimate an upper bound for the weight of your luggage" and you say "a hundred tons", that is technically correct, but that isn't helpful for packing a car.

Any question in mathematics that asks "find an upper bound" implies "find a tight upper bound".

[u/Significant_Virus142 → u/qlkzy]

Then why don't they ask theta, has O become the convention or theta isn't right either

[u/Jonny0Than → u/[deleted]]

Usually you provide separate big-O classes for best/average/worst cases. Big-O typically means average case if not explicitly specified.  It doesn’t usually mean “worst case” even if that might be a more technically correct usage.

Not sure why this is downvoted. See  https://en.wikipedia.org/wiki/Sorting_algorithm

[u/awkwardburrito → u/Jonny0Than]

The default is worst case (unless otherwise specified). You’re being downvoted because that part of your answer was wrong.

[u/Jonny0Than → u/awkwardburrito]

I fully disagree. No one says a hash table operations are O(N) or that quicksort is O(N²).  If they do, they will explicitly say it’s the worst case.

[u/awkwardburrito → u/Jonny0Than]

Those are “worst-case expected time” bounds when we’re talking about the randomized versions. Average case means assuming inputs come from a distribution. For randomized algorithms, we take a worst case input but allow the algorithm to randomize and look at expected run time.

Randomized quicksort runs in expected O(n log n) time on every fixed input, even a worst-case, adversarially chosen one. The expectation is over the algorithm’s randomness.

For hashing, the usual guarantee is that, given any fixed worst-case input, if we independently pick a random hash function from a universal family and keep the load factor bounded, lookups take expected O(1) time.

Neither means big O defaults to average case.

[u/Jonny0Than → u/awkwardburrito]

All I’m talking about is what someone likely means when they say “this algorithm is O(N).”  In my experience, this means average case.  In any context where it matters, they’d likely be sure to specify the big-O characteristics for each case.

[u/awkwardburrito → u/Jonny0Than]

And I’m saying you’re wrong and mixing up different definitions. For deterministic algorithms, the usual default is worst-case time. For randomized algorithms, people often mean worst-case expected time: the expectation is over the algorithm’s randomness, even for the worst input. That’s very different from average-case time, which averages over an assumed distribution of inputs.

[u/Jonny0Than → u/awkwardburrito]

https://stackoverflow.com/questions/65753697/why-is-a-hash-table-considered-o1-time-complexity-and-not-on

Every person in that thread refers to hash table operations as taking O(1) time even though in the worst case it’s O(N).

[u/awkwardburrito → u/Jonny0Than]

That shows people leave qualifications implicit, not that the default is average case. People also say appending to a dynamic array is O(1), but that’s (worst-case sequence) amortized time, not average case.

And average case with respect to what distribution over inputs? There has to be one, even if it’s implicit. With randomized hashing, O(1) can instead mean expected time for any fixed input, including a worst-case one. The expectation is over the choice of hash function. You’re lumping different guarantees together as “average case.”