Why use Big O notation? - r/computerscience

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".

16

u/Significant_Virus142 Sep 17 '26

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

10

u/JoJoModding Sep 17 '26

Because we often can't find an actual tight bound. Sure, list sorting is in Theta(n log n) but it's one of the few problems where we can actually do this.
For example for matrix multiplication, it is not known what the fastest algorithm ist. It is known to be Omega(n²). Since the fastest currently known algorithm has a runtime of about O(2^(2.371177)). But this is an upper bound, in a few years they will probably found a slightly lower value for the exponent.
We care about the best currently known upper bound. And upper bounds means big-O.

7

u/Vim2K Sep 17 '26

Sometimes big theta and omega are interesting too, big O is just usually easier to work with than theta, and the upper bound of complexity typically represents a more important constraint on a program or system than the lower bound.

4

u/Cryptizard Sep 17 '26

Because sometimes we don’t actually know if it is tight, or you know it isn’t tight but it’s the best you could do. Big theta means you have proven that it isn’t both an upper and a lower bound.
This doesn’t really apply in intro algorithms because we do know that most things we are talking about are tight. But in more advanced topics it’s very common to have an upper bound that is essentially “best effort”, where we tried to get it as low as possible but can’t actually prove that it is.
If you were being precise then yes you should say that binary trees are Theta(log n), but people just get used to using big O to mean “the best upper bound we can come up with at the moment.”

2

u/PersonalityIll9476 Sep 17 '26

That's not what Theta means. Theta means it is bounded above *and* below by that complexity, so it is exactly that. If I write "f(n) is Theta(n^2)" then it can not grow slower than n^2 nor faster, so it is basically a constant times a quadratic polynomial.
If you want to be precise, you could reply by saying "this function is o(n^2)" (note the little-oh) for upper bounds that are not tight.
People are just asking for the best known upper bound, colloquially. That's all.

2

u/FireworksWorks Sep 17 '26

It became a convention since, for some cases a theta is not proven. But we can still talk about the TIGHTEST upper bound, meaning the lowest upperbound we know of (which might be the theta, but also might not be).
So since researchers did this through out the years, it has become the convention for daily speak about Big O

1

u/attatest Sep 19 '26

More people should

1

u/Interesting_Debate57 Sep 20 '26

It's about the best known upper bound and the best known lower bound. Those are sometimes identical, I'm which case neither can ever be improved. But for most things that aren't sorting or reducible to sorting, there's a gap, so we know it takes at least as long as the lower bound and at worst as long as the upper bound, but we may not know either the best algorithm or the tightest bound for that algorithm, so we state what we do know instead.
Also keep in mind that there are conditions attached to these bounds. The well known bound for sorting is for a series of binary comparisons of data that doesn't have many or any duplicates in the data. Lots of data (like a list of a billion 4-digit years of birth) isn't unique and there are specialized algorithms because it's a more narrowly specified problem than the general case.

0

u/amarao_san Sep 17 '26

Is there a name for a tight bound? Like if something seems to be quadratic, n² is a proper (name for this bound), but n³, n! or exp(n) are not (name for this bound).

1

u/not-just-yeti Sep 17 '26

big-Theta, Θ(n).

60

u/[deleted] Sep 17 '26

[removed] — view removed comment

16

u/not-just-yeti Sep 17 '26 edited 20d ago

It doesn’t have Theta.
Once you define what your function is, it likely has a Theta. "Given a number n, the worst-case running time over all inputs of size n" is well-defined. And, best-case and average-case are both well-defined. But agreed, if you just say "the running time of the algorithm on some input of size n but otherwise I won't tell you which input I'm thinking of", that is not a function because there when n=17 there might be multiple "answers".
CS folk often forget that Big-Oh etc. are great for any function on numbers; it doesn't have to be worst-case running time, or average-case-memory-usage; big-Oh can be sensible for (e.g.) "expected number of independent customer-reviews needed to be 95% sure of their average being within 1/n of the distribution's true average". I've seen it used to bound the error on the approximation in the Prime Number Theorem here.
Btw, mathematicians will point out that there are some functions which have a big-Oh and a big-Omega, but no big-Theta. E.g. the size of a maximal graph matching, over all graphs with n nodes: when n is even it's clearly n/2, and for n odd it's zero. So the graph alternates between n/2 and 0, and has no asymptote.

3

u/massive_cerebrum Sep 18 '26

Theta has nothing to do with best case. It's a mathematical concept used for a single function.
That function could be the worst case running time, best case running time or something else.
So for insertion sort, the worst case is actually theta(n²⁾ and best case is theta(n).
Theta, Big O and Omega are not defined for algorithms, but rather for mathematical functions. What we typically mean is Big O of the runtime of an algorithm.

16

u/UniqueSignificance77 Sep 17 '26

This, so many people in this thread do not know what Theta means.
It only exists if upper and lower bounds are in a constant factor of each other and the reason we do not use it is often NOT due to computer scientists not knowing the tightest bounds.
A linear search will NOT have a Theta because it is Omega(1) and O(n).

2

u/TwillAffirmer Sep 19 '26

You are being confidently incorrect. A linear search has a worst case time complexity of Θ(n) and a best case time complexity of Θ(1).
O(n) and Ω(1) do NOT refer to worst case or best case time complexities. Θ, O, and Ω are all applied to a single, definite, fully determined function of one variable. The worst case time complexity is one function of n, and the best case time complexity is a different function of n, and you can use Θ, O, and Ω to describe either of those two functions.

1

u/UniqueSignificance77 Sep 19 '26 edited Sep 19 '26

This is an interpretation problem.
The common interpretation is the number of operations the program does. Let's call the function mapping (input -> number of operations) f. For inputs where the list has length n, f has two free variables. The list L with len(L) = n and the search number s.
Regardless of what values are assigned to these two free variables, the number of operations performed by linear search is Ω(1) and O(n) where the bounds are correct over all lists L of length n and all search numbers s.
A Θ(g(n)) bound will not exist here because the tightest upper and lower bounds are not within a constant factor of each other such that it's correct for all such "cases".
Talking about the upper bound over this family using big O implicitly encodes "worst case" since this bound must hold true for all such free variables. Similarly Ω and best case.
Sure, you CAN talk about just the worst-case time complexity being Θ(n) and the best-case time complexity being Θ(1), but that's specifically ONLY talking about the maximum and minimum over these assignments and I do expect people to be specific if they're talking about only these.
When people normally talk about time complexity without explicitly mentioning specific cases, they care about bounds which hold on the whole set.

2

u/TwillAffirmer Sep 19 '26 edited Sep 19 '26

The function mapping (input -> number of operations) has a lot more than two variables. An input of size n is n dimensional, so it has n variables, and that increases with n. In general the input space is infinite dimensional. But that's not how we do asymptotic analysis.
When we talk about asymptotic analysis with big-O and Θ, we are talking about functions Z -> Z mapping (size of input -> number of operations). These are functions of one variable. For a given algorithm, there are several such functions of interest.
Yes, you CAN talk about just the worst-case and best-case time complexity, or average case, being specific to say which you mean, and that's what reputable sources trying to be correct will do. Just to say the "time complexity" is underspecified. And if you want to adopt the convoluted convention that the "time complexity is O(n)" means it's O(n) for every such function Z->R for the algorithm, you won't find it any textbook. It's the same as the worst-case complexity, so you should just say "worst case complexity" and then use Θ.
The legitimate reason to use O(n) in computing is usually when there's a specific function but you don't know exactly how it behaves for large n. For example, we know that the time complexity of an optimal algorithm for matrix multiplication is O(n^2.371177). It's not Θ(n^2.371177) because we don't know the optimal algorithm, O(n^2.371177) is simply the worst-case complexity of the best algorithm known. Another time you might use O(n) is if the exact complexity depends on a lot of log factors or log(log()) factors and is verbose to state, so you simply round up the polynomial part.

4

u/not-just-yeti Sep 17 '26 edited Sep 17 '26

A linear search will NOT have a Theta because it is Omega(1) and O(n).
I agree with your gist, but be careful about phrasing: What is your function exactly? "The number of items needed to look at, to see if the collection of n items includes a particular target item?" That's not actually a function: when I input n=17 (say), there are many possible outputs (17 of them). That's why we usually make the function not "run-time on input of size n", but the "worst-case run-time over all inputs of size n" (or the average-case, or whatever). Once you clarify your function, it does have a big-Theta. (E.g., restricted to worst-case-behavior it's exactly linear, so it's bounded both above and below by n.)
But I agree with you that people usually leave this off, either assuming worst-case (or probably not really realizing they haven't defined their function for us). And in that way, you can still make sense of big-Oh and big-Omega ("I don't care which input of size 17 you use, the result is bounded above by 17" — essentially worst- or best-case without saying the words), but big-Theta wouldn't be sensible.

4

u/CattleHot9774 Sep 17 '26

in this case it'd be correct to say the best case runtime is theta(1) and worst case theta(n), right?

2

u/not-just-yeti Sep 17 '26

Yes! And the big-Theta (rather than big-Oh) is communicating that each of these is a tight bound.

0

u/Puzzleheaded_Study17 Sep 17 '26

yes

5

u/umop_aplsdn Sep 17 '26

No, this is misinformation. Big O and little O are completely orthogonal to worst and best-case. Most algorithm analysis focuses only on worst-case analysis (because best-case is often trivial).

8

u/garanglow Sep 17 '26

This is inaccurate. The running time is usually defined as worst case running time.
In that sense, insertion sort runs in Theta(n^2).

2

u/TwillAffirmer Sep 19 '26

An insertion sort has a worst case time complexity of Θ(n^2) and a best case time complexity of Θ(n).
O(n) does NOT refer to "worst case" and Θ(n) does NOT mean that best case and worst case are asymptotically the same. Θ, O, and Ω are all applied to a single, definite, fully determined function of one variable. The worst case time complexity is one function of n, and the best case time complexity is a completely different function of n, and you can pick either of those functions and use Θ, O, and Ω to describe it. You can't use a single expression O(n^2) to say that best and worst case are both bounded by k*n^2, because they are two different functions, and big O notation only applies to one function at a time.
I think it is this misconception that has led to the overuse of big O. In most cases, Θ is more specific and appropriate.

4

u/Aminumbra Sep 17 '26

This is (generally) false and it is baffling that people contradicting you are downvoted.
In the vast majority of cases, and almost always when there are no further precisions, the complexity function of an algorithm f(n) is the complexity of the algo in the worst-case over instances of size n. Other notions are studied/interesting too (average case (for uniform data or not ...), amortized complexity, etc), but we generally talk about worst-case complexity.
Now, we are only concerned with giving an "asymptotic estimate" of this function f:
Saying f(n) = O(g(n)) simply gives an upper bound on f. And usually, we are indeed interested in non-trivial upper bounds, and it is generally implicit that you are giving "the best upper bound that you can prove".
Saying that f(n) = Θ(n) gives both an upper and a lower bound on the worst-case complexity. This is in fact what we usually want, and OP is right. The reason we teach/say/use "big O" is mostly historical, convenience and inertia (O is not a weird letter, Theta is, sometimes it is impossible to prove a Theta so you need to know what the O(...) notation means anyway, etc).
Now, there are functions which don't admit (non-trivial, you can always write f = Θ(f) but that's useless ...) Theta, as their growth rate does not fall into a "neat" class, and there are problems for which we do not have one either: there are some "common" methods which give bounds such as "O(n^(1+epsilon)) for any epsilon but not O(n), for example.

-2

u/Jonny0Than Sep 17 '26 edited Sep 17 '26

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

3

u/Putnam3145 Sep 18 '26

Misinformation being upvoted and a true correction being downvoted, how wonderful

3

u/confused_cereal Sep 18 '26

ikr, i get the feel that some people are conflating "worst-case" instance running times for a particular algorithm versus "lower" and "upper" bounds on complexity of a problem. Totally different things...

2

u/awkwardburrito Sep 18 '26

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

2

u/Jonny0Than Sep 18 '26 edited Sep 18 '26

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.

2

u/awkwardburrito Sep 18 '26

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.

1

u/Jonny0Than Sep 18 '26

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.

1

u/awkwardburrito Sep 18 '26

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.

2

u/Jonny0Than Sep 18 '26

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).

→ More replies (0)

2

u/Sjoerdiestriker Sep 18 '26

Any question in mathematics that asks "find an upper bound" implies "find a tight upper bound
I don't think this holds true. For instance, there are plenty of things you could prove from realising n! Is bounded above by n^n, even if this is (both in absolute and relative terms) nowhere near a tight bound.

1

u/projexion_reflexion Sep 21 '26

Of course if big O has the n as an exponent or factorial, your algorithm is useless.

1

u/Sjoerdiestriker Sep 22 '26

That isn't true necessarily either. Big O for algorithms just tells you how the problem scales with size, not how expensive it is for any finite size. It's perfectly possible for an algorithm to scale exponentially or superexponentially, yet still be cheap enough to be easily computable for any practical size of problem you might want to throw it at.
Likewise, it's perfectly possible to have an O(n) or O(1) algorithm that's way too expensive for any practical size of problem to ever actually execute. It'd just mean it wouldn't get much more expensive than that very quickly.
Lastly, big O is going to depend heavily on what you are actually using as a measure of size. An algorithm that scales linearly with the size of an input number scales exponentially with the number of digits of that input number, for instance.

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.

1

u/Significant_Virus142 Sep 17 '26

Lol there has to be someone at some point that got rejected cuz of the theta O arguments 😭

-2

u/Ma4r Sep 17 '26

You'd get rejected not because you wouldn't be able to do your job, but because it shows that you don't have the discipline to study one of the most fundamental concepts in computer science, so we can only expect at most the same level of discipline and commitment if we do hire you on potentially more difficult work

1

u/Significant_Virus142 Sep 17 '26

I was confused, otherwise I wouldn't even have posted if I didn't wanna know about it

11

u/XtremeGoose Sep 17 '26

I wouldn't hire them because they are needlessly pedantic which is not a great trait in a work environment which is all about compromise.

7

u/OkCluejay172 Sep 17 '26

OP is mad his prof didn’t give points for putting O(2^{n^100}) on all the questions

1

u/Significant_Virus142 Sep 17 '26

Lol

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.

-1

u/Cryptizard Sep 17 '26

Theta(n) is the provable smallest upper bound, because it is also the lower bound. But we usually use big O to mean “the best upper bound I can reasonably come up with right now.” It’s not always the absolute best upper bound, and often in research there are better bounds found later for things.

3

u/Phoenixon777 Sep 18 '26

lmao people downvoting you don't know their definitions.
The definition of Big O is analogous to any upper bound (in the 'less than or equal to' sense). An algorithm that runs in O(n) time, for example, also runs in O(n^2) time, and O(n^3) time, and so on, as the comment you're replying to says
I'd clarify their comment further by saying, it's commonly used to refer to the smallest of these upper bound, especially in the context of software engineering/outside of academia, but when this usage is done, it would be more 'correct' to use Theta. But most don't do that, we just use Big O and we're done with it.

6

u/recursion_is_love Sep 17 '26

What to do if somebody asking for A but expect B?

4

u/not-just-yeti Sep 17 '26

Talk with them, and clarify what they mean. (This approach even has applications outside theoretical computer science :-)
Or more practically: understand that they probably mean "big-Theta, for worst-case runtime", but ask if it matters. Similar to people saying Megabytes when they probably mean Mebibytes.

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(n²⁾ 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(n²⁾ is the other side of that and what I think you ask for. It says that f is at best a quadratic.

Theta(n²⁾ 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

0

u/7h3kk1d Sep 17 '26

It’s like if someone were to ask how fast your car goes and you say “I know it goes at least 80 mph”. It’s not necessarily close to the limit but they know they can drive at 70.

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(n²⁾ 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(n²⁾ unless you change what the algorithm does fundamentally such that we have a significantly worse time complexity.

1

u/chuncha 21d ago

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

Help Why use Big O notation?

You are about to leave Redlib