I was looking into binary, binomial and Fibonacci heap sort and I found out that takes O(n log n) time to sort. It would be great if someone can give me a reason as to why it is so.
Why can't we sort N numbers in comparison sorting algorithm faster than O(n log n) time?
931 Views Asked by Somit At
1
There are 1 best solutions below
Related Questions in TIME-COMPLEXITY
- Time complexity of the algorithm?
- Shell Vs. Hibbard time complexity comparison
- Time complexity of swapping elements in a python list
- constant time complexity: O(x^c)
- Java TreeMap time complexity - lowerKey
- Complexity of LSD string sort (cfr. Algorithms by Sedgewick & Wayne)
- How to search a unknown composite key for dictionary in O(1) in c#
- Confusion about why NP is contained in PSPACE, EXPTIME etc
- Depth first search or backtrack recursion for finding all possible combination of letters in a crossword puzzle/boggle board?
- Time complexity of nested for loops
- TIme complexity of various nested for loops
- Best case performance of quicksort (tilde notation)
- Ranking a given list of integers in less than O(n^2)
- Bellman-Ford algorithm proof of correctness
- Division of very large numbers
Related Questions in HEAP
- Why would one use a heap over a self balancing binary search tree?
- Data structure to efficiently merge up to n elements of multiset
- How does the following comparator even works while building up the min heap?
- Would building a max heap from an Unsorted array would follow Binary Tree properties?
- std::push_heap and std::pop_heap with MoveConstructible objects
- How to use queue.PriorityQueue as maxheap
- keep keys of different heaps updated when storing links to the same objects
- Finding the running median
- Are the equations of right and left children of heap accurate?
- Formation of Binary Heaps using Arrays Shortcut
- formula for index of a children of a node in a d-ary heap
- K nearest neighbour in a 2d plane
- Kth smallest element greater than or equal to x in a min heap
- implementing data structure
- delMax() api - Priority Queue
Related Questions in HEAPSORT
- Parameter passing in C++?
- Heapsort algorithm CLRS
- Heap Sort doesn't work properly
- heapsort algorithm clarifications when sorting is actually done
- Heapsort in Java
- Ascending and Descending Heapsort
- Heapsort: Why is the right-most node of the 2nd to last level at index n/2-1?
- Heap Sort Space Complexity
- trying to write heapify algorithm - segmentation fault
- Heap sort, Understanding the basics
- Heap sort running time
- python 3 median-of-3 Quicksort implementation which switches to heapsort after a recursion depth limit is met
- heapsort coding for python 3
- compareTo with generics for heapSort
- Heapsort for any type of elements doesn't work
Related Questions in BINARY-HEAP
- Binary heap data structure - Application
- Formation of Binary Heaps using Arrays Shortcut
- Heapsort: Why is the right-most node of the 2nd to last level at index n/2-1?
- All purpose of binary heap
- Complexity characteristics of a simple heap-based array function
- Creating an Array Heap in Java
- Comparing two binary heaps and keeping track of Key, Value pairs
- increaseKey() method for Binary Heap ADT
- why new Comparable[(currentMaxIndex + 2) * 11 / 10] while construct a heap from given array?
- Ternary Heap Null Pointer Exception
- how to determine if the kth largest element of the heap is greater than x
- Should I use a Binary Heap?
- Java implement priority queue using binary heap errors
- Java creating a HeapPriorityQueue using binary heap to implement PriorityQueue
- What is the complexity for popping all n elements from a heap?
Related Questions in BINOMIAL-HEAP
- Data structure with fast insertion
- implement decreasing key in binomial heap
- Can skew binomial heaps support efficient merge?
- Why can't we sort N numbers in comparison sorting algorithm faster than O(n log n) time?
- recursion and traversing a binomial tree
- Number of nodes at depth d in binomial tree
- Printing the contents of a binomial heap in ascending/descending order
- binary heap vs binomial heap vs fibonacci heap, regarding performance for a priority queue
- If binomial heaps are represented as collections of trees, why does this implementation just have one tree?
- What's the most efficient way to convert a binomial tree into a sorted array of keys?
- Correct functional implementation on Binomial Heap
- Binomial heap: more efficient way for initial build than successive inserts?
- Implementing binomial heap
- How do I insert values into this binomial heap?
- Can binomial heap be used to find connected components in a graph?
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
A list of
nelements hasn!permutations. One of these permutations is the correctly sorted one. A single comparison between two elements conveys only 1 bit of information and therefore can't possibly do any better than cutting the search space in half. So a lower bound on the number of comparisons needed to distinguish the correctly sorted permutation from all other permutations islog2(n!) ∈ O(n log n).Note that
log2(n!)really is just a lower bound - it doesn't mean that it is actually possible to sortnnumber with exactlyceiling(log2(n!))comparisons. In fact, there are permutations for which you need a few more comparisons. But this doesn't matter if we are just interested in the asymptotic behaviour.So you see that if we don't restrict ourselves to comparison-based sorting algorithms, the lower bound doesn't hold. (See e.g. bucket sort or radix sort.)