6 added 94 characters in body
source | link

However, the running time is $O(length(S) * length(list))$$O(\operatorname{length}(S) \cdot \operatorname{length}(list))$ - for larger $S$, this will get slow, fast.

The running time for Ordering should be $O(n*log(n))$$O(n\log(n))$ where $n:=length(S) + length(list)$$n:=\operatorname{length}(S) + \operatorname{length}(list)$. Running time for binary search is $O(log(length(S)) * length(list))$$O(\log(\operatorname{length}(S)) \operatorname{length}(list))$. If $S$ and $list$ are about the same size, this simplifies to $O(n*log(n))$$O(n\log(n))$, too - but with larger constants. Only if $S$ is much bigger than $list$, binary search will be faster.

However, the running time is $O(length(S) * length(list))$ - for larger $S$, this will get slow, fast.

The running time for Ordering should be $O(n*log(n))$ where $n:=length(S) + length(list)$. Running time for binary search is $O(log(length(S)) * length(list))$. If $S$ and $list$ are about the same size, this simplifies to $O(n*log(n))$, too - but with larger constants. Only if $S$ is much bigger than $list$, binary search will be faster.

However, the running time is $O(\operatorname{length}(S) \cdot \operatorname{length}(list))$ - for larger $S$, this will get slow, fast.

The running time for Ordering should be $O(n\log(n))$ where $n:=\operatorname{length}(S) + \operatorname{length}(list)$. Running time for binary search is $O(\log(\operatorname{length}(S)) \operatorname{length}(list))$. If $S$ and $list$ are about the same size, this simplifies to $O(n\log(n))$, too - but with larger constants. Only if $S$ is much bigger than $list$, binary search will be faster.

5 added 169 characters in body
source | link

For comparison, with this S, binary search takes much longer:

GeometricFunctions`BinarySearch[S, #] & /@ tst; // AbsoluteTiming

{64.0738, Null}

The running time for thisOrdering should be $O(n*log(n))$ where $n:=length(S) + length(list)$. Running time for binary search is $O(log(length(S)) * length(list))$. If $S$ and $list$ are about the same size, this simplifies to $O(n*log(n))$, too - but with larger constants. Only if $S$ is much bigger than $list$, binary search will be faster.

The running time for this should be $O(n*log(n))$ where $n:=length(S) + length(list)$. Running time for binary search is $O(log(length(S)) * length(list))$. If $S$ and $list$ are about the same size, this simplifies to $O(n*log(n))$, too - but with larger constants. Only if $S$ is much bigger than $list$, binary search will be faster.

For comparison, with this S, binary search takes much longer:

GeometricFunctions`BinarySearch[S, #] & /@ tst; // AbsoluteTiming

{64.0738, Null}

The running time for Ordering should be $O(n*log(n))$ where $n:=length(S) + length(list)$. Running time for binary search is $O(log(length(S)) * length(list))$. If $S$ and $list$ are about the same size, this simplifies to $O(n*log(n))$, too - but with larger constants. Only if $S$ is much bigger than $list$, binary search will be faster.

4 deleted 108 characters in body
source | link

Small $S$

gives the same resultis very fast for your lists, and f[S] returns

{1, 2, 3, 4, 5}

which seems plausible to me.small $S$:

However, the running time is $O(length(S) * length(list))$ - for small $S$, this won't matter, but for larger $S$, something based on binary searchthis will be fasterget slow, fast.

Large $S$

gives the same result for your lists, and f[S] returns

{1, 2, 3, 4, 5}

which seems plausible to me.

However, the running time is $O(length(S) * length(list))$ - for small $S$, this won't matter, but for larger $S$, something based on binary search will be faster.

Small $S$

is very fast for small $S$:

However, the running time is $O(length(S) * length(list))$ - for larger $S$, this will get slow, fast.

Large $S$

3 added 2018 characters in body
source | link
2 added 68 characters in body
source | link
1
source | link