All Questions
Tagged with decision-tree sorting
4 questions
1
vote
0
answers
117
views
How many comparative sorting algorithms are there?
I've invented an abstract structure to represent a comparison-based sorting algorithm, which I will call a comparison tree (similar to the decision tree of a comparative sorting algorithm). ...
- 53
0
votes
3
answers
473
views
Can we create a decision tree for any comparison sorting algorithm even if it is very complicated?
I am reading an algorithm book.
Any comparison sort must make $\Omega(n\log(n))$ comparisons in the worst case to sort $n$ elements.
Can we create a decision tree for any comparison sorting algorithm ...
- 113
1
vote
2
answers
530
views
Why decision tree method for lower bound on finding a minimum doesn't work
(Motivated by this question. Also I suspect that my question is a bit too broad)
We know $\Omega(n \log n)$ lower bound for sorting: we can build a decision tree where each inner node is a comparison ...
user114966
1
vote
1
answer
282
views
Lower bound for merging $m$ sorted arrays (decision tree leaves count - permutations)
I need some help understanding how to calculate the lower bound on the time complexity of merging $m$ sorted arrays of length $n$.
The bound should be $nm \lg(m)$. I need to prove this using a ...
- 147