4 ms·

Ω(...) is a standard notation in complexity theory (related to O(...) notation). The meanings of the symbols there are subtle and if you don't already know them

Ω(...) is a standard notation in complexity theory (related to O(...) notation). The meanings of the symbols there are subtle and if you don't already know them, words aren't going to cut it. δ is also typical (though not "standard") for "small difference". Using conventional symbols makes it easier for people to track what they mean. You don't have to spend brain energy finding and remembering what the author said K means. Every letter in Greek and English already have multiple conventional meanings that could appear in the same papers as it is. It's just a crowded space that benefits from having more symbols. And using words instead of symbols for everything would make most expressions illegible.

ot 3y ago
> δ is also typical (though not "standard") for "small difference" No, that's epsilon. In this area, delta is usually a probability. Epsilon-delta statements are usually of the time "error > epsilon with probability < delta"
- ndriscoll 3y ago
  Epsilon and delta both often represent small changes. Epsilon typically represents an "error" size. Very often, when they appear together, delta is a small change in the input of something, and epsilon is the corresponding change in the output. So e.g. in lots of analysis proofs, you want an output error less than epsilon, and must figure out the required bound on delta to achieve that. Maybe there's a way in which your sense is an example of the above sense, but it's too early for me to think about that. In any case, in your sense, typically delta is implicitly meant to be thought of as small. Anyway, point is mathematics is a language. Like all languages, it's inseparable from its culture. The symbols often carry conventional meaning and aren't purely formal/arbitrary. This helps the speakers of that language communicate more efficiently, but it means outsiders need to learn the culture too in order to properly understand "native" level speakers. And like other languages, many parts of written mathematics just don't translate correctly to another language.
  - ot 3y ago
    > Anyway, point is mathematics is a language. Yes, and like any language there is context-dependence. In calculus you're right, epsilon and delta are usually small variations (for example in the definition of a limit). In randomized algorithms, if you say epsilon-delta anybody will immediately associate delta with an error probability.
insanitybit 3y ago
> Ω(...) is a standard notation in complexity theory (related to O(...) notation) Yeah that sucks. All of what you're saying is true and sucks. > You don't have to spend brain energy finding and remembering what the author said K means. I don't believe this is true, I believe it is the opposite. A small group of people, people who are often not the ones building the libraries from this research, know what these symbols are likely to mean. Adding a simple glossary at the top of what 'Ω' means, etc, would help. > Every letter in Greek and English already have multiple conventional meanings that could appear in the same papers as it is. Yes, that's one of the many reasons why it's a terrible practice. The same symbols can mean different things across papers.
- ndriscoll 3y ago
  I don't have a CS degree, but I'm pretty sure everyone who does was supposed to have learned what Ω means in this context. My understanding is it's standard within the field, and is a standard part of undergrad CS programs. So I'd expect that someone building libraries for data structures does understand it (or could refresh their memory). And again, with something like Ω, if you don't understand it, a glossary will not help you. It's not going to help to see "f = Ω(g) means `lim inf n->infinity f(n)/g(n) > 0`". Keep in mind this is a paper, not a tutorial on complexity theory. > Yes, that's one of the many reasons why it's a terrible practice. The same symbols can mean different things across papers. They can just like homonyms in other languages, but the meaning is usually clear from context. If you see "probabilitly 1-δ", you can expect that means "close to 100%", and probably "as close as you'd like" by tweaking some parameter that affects δ. Where there is ambiguity, the author typically spells it out. In longer works like books, authors often have an intro chapter/section where they list all of their notation even if it's completely standard with no ambiguity.
  - insanitybit 3y ago
    I don't have a CS degree either but I know what Omega means with regards to Big O. I don't think that that should really be required and I don't see why a glossary would be a problem. Omega is used for many things across many maths. > So I'd expect that someone building libraries for data structures does understand it (or could refresh their memory). Why? It's not related to the same skillset. I can and have built data structures from papers and I don't think that memorizing the greek alphabet is a useful prerequisite. > And again, with something like Ω, if you don't understand it, a glossary will not help you. No one is asking for a wikipedia quote. Just "Ω: Referring to the asymptotic complexity bound" or something like that would be fine and provide plenty of context. > If you see "probabilitly 1-δ", you can expect that means "close to 100%" How nice for you but I can not do that.

ot 3y ago

> δ is also typical (though not "standard") for "small difference" No, that's epsilon. In this area, delta is usually a probability. Epsilon-delta statements are usually of the time "error > epsilon with probability < delta"

ndriscoll 3y ago
Epsilon and delta both often represent small changes. Epsilon typically represents an "error" size. Very often, when they appear together, delta is a small change in the input of something, and epsilon is the corresponding change in the output. So e.g. in lots of analysis proofs, you want an output error less than epsilon, and must figure out the required bound on delta to achieve that. Maybe there's a way in which your sense is an example of the above sense, but it's too early for me to think about that. In any case, in your sense, typically delta is implicitly meant to be thought of as small. Anyway, point is mathematics is a language. Like all languages, it's inseparable from its culture. The symbols often carry conventional meaning and aren't purely formal/arbitrary. This helps the speakers of that language communicate more efficiently, but it means outsiders need to learn the culture too in order to properly understand "native" level speakers. And like other languages, many parts of written mathematics just don't translate correctly to another language.
- ot 3y ago
  > Anyway, point is mathematics is a language. Yes, and like any language there is context-dependence. In calculus you're right, epsilon and delta are usually small variations (for example in the definition of a limit). In randomized algorithms, if you say epsilon-delta anybody will immediately associate delta with an error probability.

insanitybit 3y ago

> Ω(...) is a standard notation in complexity theory (related to O(...) notation) Yeah that sucks. All of what you're saying is true and sucks. > You don't have to spend brain energy finding and remembering what the author said K means. I don't believe this is true, I believe it is the opposite. A small group of people, people who are often not the ones building the libraries from this research, know what these symbols are likely to mean. Adding a simple glossary at the top of what 'Ω' means, etc, would help. > Every letter in Greek and English already have multiple conventional meanings that could appear in the same papers as it is. Yes, that's one of the many reasons why it's a terrible practice. The same symbols can mean different things across papers.

ndriscoll 3y ago
I don't have a CS degree, but I'm pretty sure everyone who does was supposed to have learned what Ω means in this context. My understanding is it's standard within the field, and is a standard part of undergrad CS programs. So I'd expect that someone building libraries for data structures does understand it (or could refresh their memory). And again, with something like Ω, if you don't understand it, a glossary will not help you. It's not going to help to see "f = Ω(g) means `lim inf n->infinity f(n)/g(n) > 0`". Keep in mind this is a paper, not a tutorial on complexity theory. > Yes, that's one of the many reasons why it's a terrible practice. The same symbols can mean different things across papers. They can just like homonyms in other languages, but the meaning is usually clear from context. If you see "probabilitly 1-δ", you can expect that means "close to 100%", and probably "as close as you'd like" by tweaking some parameter that affects δ. Where there is ambiguity, the author typically spells it out. In longer works like books, authors often have an intro chapter/section where they list all of their notation even if it's completely standard with no ambiguity.
- insanitybit 3y ago
  I don't have a CS degree either but I know what Omega means with regards to Big O. I don't think that that should really be required and I don't see why a glossary would be a problem. Omega is used for many things across many maths. > So I'd expect that someone building libraries for data structures does understand it (or could refresh their memory). Why? It's not related to the same skillset. I can and have built data structures from papers and I don't think that memorizing the greek alphabet is a useful prerequisite. > And again, with something like Ω, if you don't understand it, a glossary will not help you. No one is asking for a wikipedia quote. Just "Ω: Referring to the asymptotic complexity bound" or something like that would be fine and provide plenty of context. > If you see "probabilitly 1-δ", you can expect that means "close to 100%" How nice for you but I can not do that.