X hits on this document

Powerpoint document

Lower Bounds & Sorting in Linear Time - page 25 / 28

88 views

0 shares

0 downloads

0 comments

25 / 28

Comp 122

linsort - 25

Lin / Devi

Comp 122

Analysis – Contd.

Claim:  E[ni2] = 2 – 1/n.

Proof:

Define indicator random variables.

»

Xij = I{A[j] falls in bucket i}

»

Pr{A[j] falls in bucket i} = 1/n.

»

ni =

(8.2)

Document info
Document views88
Page views88
Page last viewedWed Jan 18 12:45:59 UTC 2017
Pages28
Paragraphs427
Words1924

Comments