Computer Science Asked by user3661613 on February 7, 2021

suppose for $n$ elements we using **mergesort**.

each number compared at most $O(log n)$ = False

in average each element compared with $O(log n)$ elements = True

there exist an element compared with $Omega (log n)$ elements = True

is there anyone can share idea about these facts (i.e: why first is false and others is true).

For the first fact, consider the array $1,ldots,n,n+1,ldots,2n$. Sorting its two halves doesn't alter the array. When the two halves are merged, the element $n+1$ would be compared against all elements in the left half.

The second fact is true for every $O(nlog n)$ sorting algorithm: such an algorithm performs $O(nlog n)$ comparisons overall, and so $O(log n)$ comparisons per element on average.

The third fact is true for every comparison-based algorithm: any such algorithm must perform $Omega(nlog n)$ comparisons, and so $Omega(log n)$ comparisons per element on average; in particular, some element is compared $Omega(log n)$ times.

Finally, let us note that the AKS sorting network corresponds to a sorting algorithm which performs $O(log n)$ comparisons per element (since its depth is $O(log n)$, and each element can only be compared once in each layer).

Answered by Yuval Filmus on February 7, 2021

3 Asked on February 21, 2021 by always-newbie

1 Asked on February 20, 2021 by saku

1 Asked on February 20, 2021 by rossko_dca

1 Asked on February 17, 2021 by donvitomarco

0 Asked on February 16, 2021 by von-spotz

0 Asked on February 13, 2021 by adam-cole

a star search algorithms euclidean distance graphs shortest path

1 Asked on February 13, 2021 by aviv-barel

5 Asked on February 10, 2021 by gizmo

0 Asked on February 10, 2021 by arthur-b

1 Asked on February 8, 2021 by keith-paton

1 Asked on February 7, 2021 by user3661613

1 Asked on February 6, 2021 by builderthebob00

0 Asked on February 5, 2021 by pookie

1 Asked on February 4, 2021 by retsek680

1 Asked on February 3, 2021 by stark2022

0 Asked on February 1, 2021 by david-grnberger

0 Asked on January 30, 2021 by tzlil

0 Asked on January 29, 2021 by angelic-demonic

Get help from others!

Recent Questions

- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?
- Does Google Analytics track 404 page responses as valid page views?

Recent Answers

- Peter Machado on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?

© 2023 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP