X hits on this document

Powerpoint document

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

93 views

0 shares

0 downloads

0 comments

9 / 28

Comp 122

linsort - 9

Lin / Devi

Comp 122

Proof – Contd.

n! l 2h or 2h   n!

Taking logarithms, h lg(n!).

n! > (n/e)n. (Stirling’s approximation, Eq. 3.19.)

Hence, h lg(n!)

                lg(n/e)n

               = n lg nn lg e

               = (n lg n)

Document info
Document views93
Page views93
Page last viewedThu Jan 19 07:13:35 UTC 2017
Pages28
Paragraphs427
Words1924

Comments