Closed-form Expression of the Expected value of the Cost of D&C Algorithm? Let there is a binary-string, $B$, of length $N$. The probability of occurrence of 0 and 1 in this binary-word is $p$  and $q$ , respectively. Each bit in the string is independent of any other bit.

There is an algorithm (divide and conquer) which finds the location of 1’s in a given binary-string, in Q # of steps (cost).

I am looking for some close-form solution of the expected # of steps,$E[Q]$, with given probabilities $p$ and $q$ for a string of length $N$.

For instance, for $N=4$ the cost ,${{Q}_{i}}$,  for each possible word is:
[\begin{matrix}
   {{B}_{i}} &amp; {{Q}_{i}} &amp; {{P}_{i}}  \\
   0000 &amp; 1 &amp; {{p}^{4}}  \\
   0001 &amp; 5 &amp; {{p}^{3}}q  \\
   0010 &amp; 5 &amp; {{p}^{3}}q  \\
   0011 &amp; 5 &amp; {{p}^{2}}{{q}^{2}}  \\
   0100 &amp; 5 &amp; {{p}^{3}}q  \\
   0101 &amp; 7 &amp; {{p}^{2}}{{q}^{2}}  \\
   0110 &amp; 7 &amp; {{p}^{2}}{{q}^{2}}  \\
   0111 &amp; 7 &amp; p{{q}^{3}}  \\
   1000 &amp; 5 &amp; {{p}^{3}}q  \\
   1001 &amp; 7 &amp; {{p}^{2}}{{q}^{2}}  \\
   1010 &amp; 7 &amp; {{p}^{2}}{{q}^{2}}  \\
   1011 &amp; 7 &amp; p{{q}^{3}}  \\
   1100 &amp; 5 &amp; {{p}^{2}}{{q}^{2}}  \\
   1101 &amp; 7 &amp; p{{q}^{3}}  \\
   1110 &amp; 7 &amp; p{{q}^{3}}  \\
   1111 &amp; 7 &amp; {{q}^{4}}  \\
\end{matrix}]
From the discrete probability theory, we can evaluate the expected cost of the above case ,$N=4$,as follow $\begin{align}
  &amp; \therefore E[Q]=\sum\limits_{i=0}^{{{2}^{N}}-1}{{{Q}_{i}}({{p}^{N-i}}}{{q}^{i}}) \\ 
 &amp; \Rightarrow E[Q]=\sum\limits_{i=0}^{15}{{{Q}_{i}}({{p}^{N-i}}}{{q}^{i}}) \\ 
 &amp; \Rightarrow E[Q]={{p}^{4}}+4\times 5\times {{p}^{3}}q+2\times 5\times {{p}^{2}}{{q}^{2}}+4\times 7\times {{p}^{2}}{{q}^{2}}+4\times 7\times p{{q}^{3}}+1\times 7\times {{q}^{4}} \\ 
 &amp; \Rightarrow E[Q]={{p}^{4}}+20{{p}^{3}}q+10{{p}^{2}}{{q}^{2}}+28{{p}^{2}}{{q}^{2}}+28p{{q}^{3}}+7{{q}^{4}} \\ 
\end{align}$ 

However, for very large values of N, say 1024, it is computationally not possible to evaluate the cost of each possible binary string (i-e ${{2}^{1024}}=\text{1}\text{.79}\times \text{1}{{\text{0}}^{308}}$ binary words). So, this is the problem I am stuck in. 

Is it possible to deduce some analytical/ close-form expression for evaluating the expected value of the cost of this algorithm for a given length N and probabilities p and q (instead of brute-force method defined above)?

I will be very thankful, if someone could help in this regard.

ADDITIONAL INFORMATION:

Divide &amp; Conquer Algorithm:
    Lets take 0000 0001, for instance:


First question: Is it (i-e 0000 0001) equal to ZERO (i-e 0000 0000) ? The answer is No, for our case. 
Then divide the original 8 bit word into two 4 bit segments, and again ask the same question for each of the two 4 bit words. So for our case it would be YES for the first segment (0000) and NO for the other segment (0001)?
Now, this time I will be questioning only the segment where I got NO. In our case it was 0001. Then, I will now again divide this 4-bit segment into two segments and pose the same question. Hence, is 00 equal to ZERO? answer : YES. For the other segment , 01, the answer is NO.
This is the final step. I will again divide the 2-bit word into two 1-bits, i-e 0 and 1. So, my first question: is 0 equal to 0? answer is YES. And for the other remaining bit, is 1 equal to 0? Answer is NO.


So, I asked a total of 7 questions to find the location of 1 in a binary word of 0000 0001. Similarly, we will go through other binary words.

Efficient Way for evaluating the cost of Above algorithm:
(courtesy to Yuval Filmus)

Here is how to calculate the cost of the algorithm. Start with the bit vector $x$, and consider the following operation $O$, which divides $x$ into pairs of bits and computes their ORs. Thus $|O(x)| = |x|/2$. Compute a sequence $O(x),O(O(x)),O(O(O(x))),\ldots$ until you get a vector of width $1$. Count the total number of 1s in the sequence. If you got $N$, then the cost is $2N+1$.

For example, suppose $x=0101$. Then the sequence is
$$ 11,1, $$
and so $N = 3$ and the cost is $7$.
Expectation is additive, so your expectation equals
$$ E := 2E[w(O(x))] + 2E[w(O(O(x)))] + \cdots + 2E[w(O(\cdots(x)\cdots))] + 1, $$
where $w(\cdot)$ is Hamming weight.
Let's calculate $E[w(O(x))]$, again using the fact that expectation is additive. The probability that the $i$th bit of $O(x)$ is $1$ is exactly $1-p^2$, and there are $N/2$ of them, therefore $E[w(O(x))] = (N/2)(1-p^2)$. Similarly, the probability that the $i$th bit of $O(O(x))$ is $1$ is exactly $1-p^4$, and there are $N/4$ of them, and so $E[w(O(O(x))] = (N/4)(1-p^4)$. If $N = 2^n$, then we get
$$ E = 2^n (1-p^2) + 2^{n-1}(1-p^4) + \cdots + 2(1-p^{2^n}) + 1.$$
We can simplify this slightly by summing the geometric series:
$$ E = 2^{n+1}-1 - 2^n p^2 - 2^{n-1} p^4 - \cdots - 2p^{2^n}. $$