# Find ii-th number in unsorted sequence in logspace (deterministic turing machine)

There is given input – words is sequence of numbers: $w_i$ is number
in sequence, $i$ is position. All of them are in written in binary
system.

Prove that there exists deterministic
Turing machine which find $i$-th number in sorted sequence $w$ in
logspace.

I am not sure if I correctly solved it, so I ask for checking my reasoning. It seems to be fairly simple.

First of all, what we can do in logspace:
compare two numbers
iter over sequence (move to $n$-th number)

Simply, we consider one by one each element of sequence and count how many elements is less than currently considered. If we count $i-1$ numbers, then we stop. It requires logarythmic($k$) memory for counter. These counter can be reused (for each iteration).

Waht do you think ? Maybe some other approach to proving it ?

First let’s consider the case when numbers are unique. The idea is that for each element $w_t$ we count the number of elements in the sequence which are less than $w_t$. After each loop on all elements of the sequence we check if there are $i-1$ elements less than $w_t$ then $w_t$ must be $i$-th element in the sorted sequence, so we halt with the output equal to $w_t$.

proc(w, k, i)
for t=0 to k
counter = 0
for j=0 to k
if w[t] > w[j]
counter = counter + 1
if counter == i-1 then output w[t] and halt
end-proc


Now, if numbers are not unique then we have to count duplicates as well

proc(w, k, i)
for t=0 to k
counter = 0
dups = 0
for j=0 to k
skip if j == t
if w[t] == w[j]
dups = dups + 1
for j=0 to k
if w[t] > w[j]
counter = counter + 1
if counter+1 <= i AND i <= counter + dups+1
then output w[t] and halt
end-proc


  w[1] w[2] ... w[counter] w[t] w[t] ... w[t] ..
\__________  __________/     \_____  ____/
\/                      \/
all elements less than w[t]   duplicates


Both procedures require only constant number of variables i, j, k, counter, and dups whose lengths are $O(\log(k))$. Your solution is similar to these algorithms so your approach is correct.