2

I am reading the paper Linear Work Suffix Array Construction by Juha Karkkainen, Peter Sanders, Stefan Burkhardt, and in a number of places they use the notation $$(0,v].$$ I assumed it was a mistake, but they use it a number of times. What does it mean?

T. Eskin
  • 8,303
superbriggs
  • 175

2 Answers2

4

Looks like the interval from $0$ to $v$, excluding $0$ but including $v$.

  • $[0,1]$ includes both $0$ and $1$
  • $[0,1)$ includes $0$ and excludes $1$
  • $(0,1]$ excludes $0$ and includes $1$
  • $(0,1)$ excludes both $0$ and $1$

Half-open intervals (the middle two types) are very common in computing contexts, although you usually see half-open the other way (i.e. $[a,b)$). They're convenient due to how they combine: e.g. the disjoint union of $[a,b)$ and $[b,c)$ is $[a,c)$, and appear in common programming style, e.g. in C one usually writes a for loop as

for(i=0; i < 10; ++i)

to include the ten integers from $0$ through $9$: i.e. the interval $[0,10)$ of integers.

4

$(0,v]$ is the set of numbers between $0$ and $v$, where $0$ is never reached. In other words : $(0,v] = \{ x | 0<x\le v\}$. It is also written $]0,v]$.

Alan Simonin
  • 1,056