Counting heads. Given integersn and k, along with ${\mathit{p}}_{\mathbf{1}}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}{\mathit{p}}_{\mathbf{n}}\mathbf{}\mathbf{}\mathbf{\in }\mathbf{}\left[0,1\right]$, you want to determine the probability of obtaining exactly heads when biased coins are tossed independently at random, where pi is the probability that the ith coin comes up heads. Give an $\mathbf{0}\left(n^2\right)$algorithm for this task. Assume you can multiply and add two numbers in $\left[0,1\right]$in $\mathbf{0}\left(1\right)$time.

Let us consider that n-1 coins are already tossed together and n^th coin is toss separately.

Now let $P\left(1...n,k\right)$ is the probability of getting exactly ‘k’ heads when ‘n ’ coins are tossed.

Now applying our consideration, we will define a storing table $n*k$and fill the various probability.

Thus there are two ways of getting exactly ‘k ’ heads with ‘n ’ coins:

• If $n-1$coins have $k$heads and $n$^th coin show tail.
• If $n-1$coins have $k-1$heads and $n$^th coin is head.

According to the above two cases, we can define our subproblem as:

$\mathbf{P}\left(n,k\right)\mathbf{=}\mathbf{P}\left(n-1,k\right)\mathbf{*}\left(1-p\left[n\right]\right)\mathbf{+}\mathbf{P}\left(n-1,k-1\right)\mathbf{*}\mathbf{p}\left[n\right]$

If we are tossing first $i$coins, where $j$is the number of heads,

And L(i,j) as total probability of getting head,

localid="1657267432115" $\mathbf{L}\left(i,j\right)\mathbf{=}\{\begin{array}{l}{P}_i*L\left(i-1,j-1\right)+\left(1-p_i\right)*L\left(i-1,j\right);\mathrm{for}j=0,1..i\\ 0;\mathrm{for}j\le 0\end{array}$

On solving this recursion equation, the time complexity will be $0\left(nk\right)$.

This is because our algorithm will run for ‘n’ coins but will stop if it gets k heads. So we will be using first loop for to toss each coin which would be ‘n’ and then second loop will check for head in the tossed coin.