Combinatorial problem on finding the index associated to an edge of a complete graph Ok so here is a combinatorial problem that I thought of. 
Suppose N is in $\mathbb N$ such that $N>1$, then there is a way to count (set an index)
to all pairs $(i,j) \in \{1,\dots,\mathbb N\}\times\{1,\dots,\mathbb N\}$ such that $i<j$. This problem is the same as the problem of setting a unique index to the edges of a complete undirected graph with $N$ vertices. In total there are $N(N-1)/2$ such pairs and the counting function can be given by 
$$f:S\rightarrow \{1,\dots,N(N-1)/2\} \qquad f((i,j)):= \sum_{k=2}^i (n-k+1) + (j-i)$$
where $S := \{(i,j) : 1\leq i,j\leq N$ and $i<j\}$ and those under the summation notation is ignored if $i=1$.
This function is a bijection and you do get for a pair $(i,j)$ a unique number $f(i,j)$ less or equal to $N(N-1)/2$. 
The question is how to find the inverse of this function, i.e. if $x$ is a number in the image of $f$ then what is the $(i,j)$ associated to $x$. In other words, given the index of the edge can I easily find the pairs that present the vertices of the complete graph. You will end up with a quadratic equation with respect to $i$ but the condition $i<j$ will also give us a $j$. But what is the formula for the inverse of $f$?
 A: First of all, for this kind of monotonic functions you can usually effectively use binary search, which would calculate the solution in logarithmic time with respect to the space size (assuming you can calculate where "half of the subspace" roughly is). As you can calculate your sum (after some simplifications) in constant time (or $O(\log N)$ for arbitrarily big numbers), that algorithm would work in $O(\log N)$ time (or respectively in $O(\log^2 N)$).
Second, you can derive a more direct formula. More precisely, observe that (using a formula for the area of a trapezoid):
$$f\big((i,j)\big) = \frac{1}{2}(N-1 + N-i+1)\cdot(i-1) + (j-i)$$
Here we will use the Newton's method to calculate $i$ out of $v$ using $g_v(x) = f(x,x)-v$:
$$x_{n+1} = x_n - \frac{g(x_n)}{g'(x_n)} = x_n - \frac{\frac{1}{2}(2N-x_n)\cdot(x_n-1)-v}{N-x_n+\frac{1}{2}}$$
After we recover the solution $x = g_{v-1}^{-1}(0)$ with a reasonable accuracy, you can calculate $j$ by using $j = v-f(\lfloor x\rfloor,\lfloor x\rfloor)$. The $-1$ in $v-1$ in $g_{v-1}$ was added because $j > i$.  I didn't do any convergence analysis, but my guess is only a few steps are enough for any reasonable $N$ (for square roots 6 are enough for $N<2^{64}$, for arbitrarily big numbers $O(\log N)$).
Third, you can find a bijection which is more inverse-friendly, for example see my answer here.
I hope this helps $\ddot\smile$
