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
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP