12.19

Initially the “all–zero” basis state has probability [math]p_{0}=2^{-n}[/math]. If one application of Jack[math](Q,0^{n})[/math] simply “doubles” that probability, then after k calls we have [math]\displaystyle p_{k}=2^{k}\,p_{0}=2^{k-n}. [/math]
We need the first k for which [math]p_{k}\ge \tfrac12[/math]: [math]\displaystyle 2^{k-n}\;\ge\;\tfrac12 \;\Longrightarrow\;k-n\;\ge\;-1 \;\Longrightarrow\;k\ge n-1. [/math]
Hence Number of Jack calls required: Θ(n), more precisely [math]n-1[/math] (and the next integer if fractional).

Back to Chapter 12