Pergunta

Problem

Given a search algorithm that can be used to query a k-dimensional space, produced from an input array of N data, has a time complexity of $O(klog^2N)$. This algorithm partitions the space into four regions then selects three of those regions due to some condition. From there it selects at random one of the three spaces as the next space to check for the answer. If this algorithm produces a value it is 100% the correct solution, else it states it cannot find the solution which is always wrong because the item being searched is always there. Therein, the theory is to run it a bunch of times until it produces the solution.

Question

I created this algorithm which is to be utilized as an experiment to create a BPP algorithm for a data analysis problem. But, I am uncertain if it qualifies as a BPP algorithm. From my understanding it is not, because it has a one in three chance of selecting the correct partition at each time it partitions the space. This means the probability of selecting the correct solution is $(1/3)^{klogN}$ making the probability of selecting the incorrect solution one minus the probability of the correct solution.

So, my question is A) Is my interpretation correct for measuring the probability? B) Does this algorithm qualify as a BPP algorithm or some other class?

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top