3 ms·
Even rational numbers which have repeating digits at the end are not O(1) because in order to calculate the n-th digit you need to calculate n modulo k where k
by kdkdk 4y ago
Even rational numbers which have repeating digits at the end are not O(1) because in order to calculate the n-th digit you need to calculate n modulo k where k is the length until the number repeats its digits, which needs to read the entire input number n (thus runs in O(log(n)).
The only exception are rational numbers with k being a power of two.
Take 0.1010101010…, you can get the n-th digit by reading off the smallest digit of n and checking whether it is a 0 or a 1.
There are transcendental numbers where the n-th digit can be computed in O(log n) like Champerowne constant though.