I have written the following algorithm

  • $select(\Pi)$ select the first elements from $\Pi$. When there are no element in $\Pi$, it return $\emptyset$. Always terminates .Worst case complexity $O(1)$
  • $processing(e)$ function take a element $e$ as input and process it. And based on the processing it either output element $r$ or $\emptyset$. Always terminates. Complexity not known.
  • $update(r,\Pi,\Delta)$ function take $r,\Pi,\Delta$ as input and update criteria in the function. And based new criteria, it transfer already processing element from $\Delta$ to $\Pi$. Always terminates. Worst case complexity $O(sizeof(\Pi+\Delta))$

$\textbf{Input} - \textbf{a set of elements $\Pi$}$

$\textbf{Output} - \textbf{a set of elements $C$}$




$\textbf{While}$($e \not=\emptyset$){


$\hspace{10mm}\textbf{if}$($r \not=\emptyset$){

$\hspace{20mm} C$=$C\cup r$;

$\hspace{20mm} \Pi$=$\Pi-e$;

$\hspace{20mm} \Pi,\Delta$=$update(r,\Pi,\Delta)$;


$\hspace{20mm} \Pi$=$\Pi-e$;

$\hspace{20mm} \Delta$=$\Delta\cup e$;




$\textbf{return}$ $C$;

Proof Sketch ---- The termination condition of the algorithm - when $\Pi$ is $\emptyset$. Each iteration of the loop involves a $processing$ call which always terminates. Because $processing$ does not return any results for 10 seconds, then algorithm terminates the $processing$ call and return $\emptyset$. We can say that the algorithm always terminates since the size of $\Pi$ and $\Delta$ move in a monotone way up and down respectively, and one always moves. Thus, eventually $\Pi$ become empty and the algorithm terminates.

Can anyone please suggest to me how I can formally complete the proof?

Can anyone please suggest how we can compute the worst case complexity as we do not know the complexity of the $processing$ function? How we can use Oracle for $processing$ function in that process?

  • 1
    $\begingroup$ Also, perhaps it is just obvious from the question text, but what exactly it is you are trying to prove? That all your claims preceding the algorithm (i.e., its specification) are correct? Or just what is stated in the question's title? $\endgroup$ – dkaeae Mar 29 '19 at 15:29
  • $\begingroup$ I need a suggestion whether my Proof Sketch is correct for this algorithm. If you yes how I can construct the proof? Is any other information we need to consider to complete the proof. $\endgroup$ – Tom Mar 29 '19 at 15:59
  • $\begingroup$ I am updating question by removing the image. Thanks for your suggestion $\endgroup$ – Tom Mar 29 '19 at 16:00
  • $\begingroup$ I think you have not stated enough hypotheses to guarantee termination. It could be the case that processing always returns $\emptyset$, and in that case we get stuck into an infinite loop. $\endgroup$ – chi Mar 29 '19 at 16:50
  • $\begingroup$ Extremely sorry. There is a typo I have updated the algorithm. $\endgroup$ – Tom Mar 29 '19 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.