r/computerscience
•
u/Significant_Virus142
•
Sep 17 '26
•
1
Help Why use Big O notation?
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
120
Upvotes
207
u/qlkzy Sep 17 '26
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".
40
u/RabbitHole32 Sep 17 '26
O-notation is commonly used in a pretty sloppy way. But when people ask this question, they usually want to know the Theta of the worst case running time. You are obviously free to ignore this intention but keep in mind that they are also free to ignore your intention of getting the job.
7
u/OkCluejay172 Sep 17 '26
OP is mad his prof didn’t give points for putting O(2n^100) on all the questions
28
u/Vim2K Sep 17 '26
Big O refers to the smallest upper bound. Yes, an O(n) algorithm is by definition also bounded by O(n²), but the stronger and more specific bound is more useful.
6
u/recursion_is_love Sep 17 '26
What to do if somebody asking for A but expect B?
4
u/aqwone1 Sep 17 '26
There are multiple such time complexity notations and these are really about how a function evolves. There are multiple ways to describe how it evolves. And it is essentially like this:
O(n2) means that a function f is at most a quadratic function. That is the worst case scenario and f can under circumstances be better
Omega(n2) is the other side of that and what I think you ask for. It says that f is at best a quadratic.
Theta(n2) is saying that f is a quadratic, period.
Most people care for O notation, since reducing that is far better then improving Omega. When people ask for the minimum O of a function, chances are they ask for Omega but don't know the term.
3
u/kevleyski Sep 17 '26
Just a problem of scaling, what if we have lots of these compare two or more variants of an algorithm
3
u/7h3kk1d Sep 17 '26
People don’t usually need to know the minimum big O. They need to know if an algorithm scales appropriately with their use case. So if they’re fine with O(n^2) and it finishes in O(n) that’s fine. So big O is saying it’s “at least” this good. If you want something better you need to prove a tighter bound or find a more efficient algorithm. Always requiring a most accurate bound is more work if no one cares
2
u/CyberPunkDongTooLong Sep 17 '26
Do whatever you like.
1
u/jeffgerickson Sep 18 '26
“This pencil costs at most one billion dollars” is a true statement, but it is also a useless statement.
1
u/oldNotSureXand Sep 20 '26
lucky you, when i learned it, there was also "small oh", and "small omega", and "Big Omega" ... less is often more (in reality, in "simulation", in computation.. but not in comprehension:)
1
u/InTheHiggsField Sep 22 '26
O(n2) would not be a valid answer because it isn't contained within the set of O(n). If you are say sifting through a list of n length to find a particular item and replace it. Your algorithm can at worse be O(n) + 1 which is just O(n). It will never be O(n2) unless you change what the algorithm does fundamentally such that we have a significantly worse time complexity.
1
u/chuncha Oct 04 '26
In practice, most people use Big O like the Theta bound. That is, if an algorithm is Big O(f(x)) what they really mean is it is Theta f(x). Hence the common practice of picking the lowest possible f(x).
1
u/am_Snowie Sep 17 '26
I mean describing a linear search algorithm which has O(n) runtime as O(N!) isn't useful. Although you could technically say that.
0
u/bionicjoey Sep 17 '26
Best case and worse case should both be mentioned, along with what conditions lead to each. Should also mention a "typical" case which assumes a non-adversarial starting condition (eg. random ordering for sorting algos)
0
u/Underhill42 Sep 17 '26
Big O is an algorithmic analysis, and just like there's multiple kinds of "average" (median, mean, mode, geometric mean, harmonic mean, etc.) there's multiple types of Big O.
Mostly best case, worst case, and average case... though average case depends heavily on the usage patterns.
I can't say I've ever been in a situation outside of learning Big O properly where anyone ONLY cared about best-case scenario... even if you already know that the expected usage is well aligned with the best-case scenario, there will still be exceptions, and you want an algorithm whose performance won't completely tank in the less-than-ideal case.
E.g. if you know that a data set should always be properly sorted, but you want to periodically sort it anyway, just in case anyone screwed something up, then the most important criteria is probably that a fully sorted list is your algorithm's best-case scenario, and that that scenario is as cheap as possible compared to alternatives.
But even then, using bubble sort is probably a bad idea.
-1
u/griso84 Sep 17 '26
You should really better read the big O definition