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?
934 Views Asked by Somit At
1
There are 1 best solutions below
Related Questions in TIME-COMPLEXITY
- C++ : Is there an objective universal way to compare the speed of iterative algorithms?
- Simplify complexity
- How to find big o of dependent loops and recursive functions?
- find number of unique durations given a list of durations and an upper bound
- What is the time complexity of doing two binary searches on an array?
- How to determine the time complexity of a recursive function that has a loop enclosed in it?
- Why is time complexity of Generate Parentheses O(4^n ( sqr root( n)))
- Find median in constant time O(1)
- Best Index - HackerEarth Solution, help me optimize the code
- Time complexity of Insertion Sort of an array of n numbers, with additional information
- How come checking for printable bytes is faster with the "in" operator rather than interval comparisons?
- Generate cuboids with integer sides and diagonals: how to improve the time complexity?
- What is the time complexity of this algorithm with two arrays?
- calculating number of operations in algorithm
- Time complexity of Rectangle Covering algorithm
Related Questions in HEAP
- OneDrive API Upload Large File
- I found a working code to insert a node at a heap implemented in array in C++ and I wonder why does the code work despite incrementing the size array
- Efficient list sorting: Using heap instead of standard sorting is slower
- Implementing a max heap in python using heapq for a custom class object with custom comparators in Python?
- Sorting sums of two numbers in an effective way
- An algorithm to find the shortest path based on 2 criteria
- At which levels in a max-heap might the `k`-th largest element reside?
- Incorrect Result Order with PHP Heaps
- Efficient Implementation of Priority Queue with Constant-Time Extraction of the Minimum Element
- Why we should use sink to construct the heap in heapsort rather than swim?
- Why does my code generate the "Debug Assertion Failed! _CrtIsValidHeapPointer(block)" error?
- Sliding Window Median Two Heaps Method in Python, TLE Error
- How to properly prioritize priority queue heap in ascending order in C?
- Unsure of course content validity
- Transforming Heaps
Related Questions in HEAPSORT
- Heap sort with multithreading
- How to solve the recurrence for Heapify with repeated backward substitution?
- Idea for improving heapsort
- Why are Heaps ALMOST complete binary tree?
- Mini-Heap Sort implementation in JavaScript
- Implementing Heap Sort from Scratch
- Warning in C: passing argument from incompatible pointer type
- Distinguishing between sorts using only the executable
- Questions about William's Heapsort
- A three dimensional bubble sort algorithm?
- Trouble with extracting maximum value from Max Heap using JavaScript
- Issue with setheap in Heapsort
- How to implement heapsort?
- How does std::sort_heap break the heap property?
- Treap Data Structure assistance. Some of my nodes do not seem to be printing
Related Questions in BINARY-HEAP
- Prove that the number of comparisons between elements in binary heap build is at most (2N-2)
- Rust remove one instance of a value from a BinaryHeap
- How to identify vertices that violates Max Heap property?
- Binary heap output not as expected
- Give an algorithm that finds an arbitrary item X in a binary heap using at most roughly 3N/4 comparisons
- Ideal way to handle integer overflows in Golang on different platforms
- Why do we need binary heaps when we have binary search trees?
- Is Dijkstra faster when using Fibonacci Heap?
- why are binary heaps a tree structure?
- [Heap]- after removing a node, should you run siftDown for all nodes or just the root?
- Order Notation of pop-max in a binary heap
- Max Heap built with pimpl in c++ not working properly
- Binary Heap get_parent() function in Python not working as expected
- Checking if Inserting values in order into an initially empty minimum binary heap is correct
- Time complexity of building a heap relative to two arguments, N and M
Related Questions in BINOMIAL-HEAP
- Delete and Increase key for Binomial heap
- Binomial heap sibling - linked list reversal
- Binomial Min Heap delete issue
- Why can't we sort N numbers in comparison sorting algorithm faster than O(n log n) time?
- Can skew binomial heaps support efficient merge?
- Creating a binomial heap from an array?
- Number of nodes at depth d in binomial tree
- recursion and traversing a binomial tree
- Can binomial heap be used to find connected components in a graph?
- Idris not recognizing equivalant types
- DRAWING Binomial Heap
- What's the most efficient way to convert a binomial tree into a sorted array of keys?
- Printing the contents of a binomial heap in ascending/descending order
- How do I insert values into this binomial heap?
- Counting the number of nodes in certain level binomial heap
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 # Hahtags
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.)