Don how well a deterministic algorithm does depends upon what the deterministic algorithm is and what the input is, it cannot always query O(1) queries.
E.g. in a 20 bit case
If the deterministic algorithm starts its queries from the beginning, querying each bit in turn and this is pattern is always
00000111110000000000
It will always take n/4+1 queries. Only when the input is random will it on average take O(1) queries.
The random one will take O(1) on average on every type of input.
Don how well a deterministic algorithm does depends upon what the deterministic algorithm is and what the input is, it cannot always query O(1) queries.
E.g. in a 20 bit case
If the deterministic algorithm starts its queries from the beginning, querying each bit in turn and this is pattern is always 00000111110000000000
It will always take n/4+1 queries. Only when the input is random will it on average take O(1) queries.
The random one will take O(1) on average on every type of input.