ALBERT — All Library Books, journals and Electronic Records Telegrafenberg

Hits per page

hit 1 - 1 | 1 hit

Sorting

Electronic Resource

Average-Case Analysis of the Merging Algorithm of Hwang and Lin (1998)

Fernandez de la Vega, W. ; Frieze, A. M. ; Santha, M.

Springer

Algorithmica 22 (1998), S. 483-489

add to mindlist on the mindlist

Details

ISSN: 1432-0541

Keywords: Key words. Merging, Average-case analysis.

Source: Springer Online Journal Archives 1860-2000

Topics: Computer Science , Mathematics

Notes: Abstract. We derive an asymptotic equivalent to the average running time of the merging algorithm of Hwang and Lin applied on two linearly ordered lists of numbers a 1 〈a 2 〈. . . 〈a m and b 1 〈b 2 〈 . . . 〈b n when m and n tend to infinity in such a way that the ratio $ \rho $ = m/n is constant. We show that the distribution of the running time is concentrated around its expectation except when $ \rho $ is a power of 2. When $ \rho $ is a power of 2, we obtain an asymptotic equivalent for the expectation of the running time.

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1007/PL00009235

Permalink

	Location	Call Number	Expected	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit