Analysis of successful search The expected number of elements examined in a successful search Is E 1+>X 1+>E|X ∑|1+2 1+ n m:=1
Analysis of successful search The expected number of elements examined in a successful search is 11 11 1 1 1 1 nn nn ij ij i ji i ji E X EX n n = =+ = =+ ⎡ ⎤ ⎛ ⎞⎛ ⎞ ⎢ ⎥ + =+ ⎡ ⎤ ⎜ ⎟⎜ ⎟ ⎣ ⎦ ⎢ ⎥ ⎣ ⎦ ⎝ ⎠⎝ ⎠ ∑∑ ∑∑ 1 1 1 1 1 n n n m i ji = =+ ⎛ ⎞ = + ⎜ ⎟ ⎝ ⎠ ∑ ∑ ( ) 1 1 1 n i n i nm = = + − ∑ 1 1 1 1 n n i i n i nm = = ⎛ ⎞ =+ − ⎜ ⎟ ⎝ ⎠ ∑ ∑
Analysis of successful search(cont The expected number of elements examined in a successful search Is E|21+∑X=1+ Envy n(n+ 1+ 1) =1+ 22 =(1+a)
Analysis of successful search (cont.) The expected number of elements examined in a successful search is 1 1 11 1 1 1 1 n n nn ij i ji i i E X ni n nm = =+ = = ⎡ ⎤ ⎛ ⎞ ⎛ ⎞ ⎢ ⎥ ⎜ ⎟ + =+ − ⎜ ⎟ ⎢ ⎥ ⎝ ⎠ ⎝ ⎠ ⎣ ⎦ ∑ ∑ ∑∑ 1 ( 1) 2 1 2 n n n nm ⎛ ⎞ + =+ − ⎜ ⎟ ⎝ ⎠ 1 1 2 n m − = + 1 2 2 n α α =+ − = Θ + (1 ) α