Algorithm Complexity Analysis for Variable Length Queue BFS
<p>I have developed an algorithm that is kind of a variation of a BFS on a tree, but it includes a probabilistic factor. To check whether a node is the one I am looking for, a statistical test is performed (I won't get into too much detail about this). If the test result is positive, the node is added to another queue (called <code>tested</code>). But when a node fails the test, the nodes in the <code>tested</code> need to be tested again, so this queue is appended to the one with the nodes yet to be tested.</p>

<p>In Python, considering that the queue <code>q</code> starts with the root node:</p>

<pre><code>...
tested = []
while q:
    curr = q.pop(0)
    p = statistical_test(curr)
    if p:
        tested.append(curr)
    else:
        q.extend(curr.children())
        q.extend(tested)
        tested = []
return tested
</code></pre>

<p>As the algorithm is probabilistic, more than one node might be in <code>tested</code> after the search, but that is expected. The problem I am facing is trying to estimate this algorithm's complexity because I can't simply use BFS's complexity as <code>q</code> and <code>tested</code> will have a variable length.</p>

<p>I don't need a closed and definitive answer for this. What I need are some insights on how to deal with this situation.</p>

<p>The worst case scenario is the following process:</p>

<blockquote>
  <ol>
  <li>All elements <em>1 : n-1</em> pass the test and are appended to the <code>tested</code> queue.</li>
  <li>Element <em>n</em> fails the test, is removed from <code>q</code>, and <em>n-1</em> elements from <code>tested</code> are pushed back into <code>q</code>.</li>
  <li>Go back to step 1 with <em>n = n-1</em></li>
  </ol>
</blockquote>

<p>This is a classic O(n<sup>2</sup>) process.</p>

python algorithm time-complexity analysis