All Questions
Tagged with decision-tree lower-bounds
9 questions
0
votes
0
answers
50
views
Definition of an algebraic decision tree
I am trying to understand what an algebraic decision tree is but wikipedia lacks a formal definition, just an intuition. So I need to check if my understanding is correct.
From what I have read it ...
- 341
0
votes
0
answers
255
views
How to prove that the lower bound of the Huffman coding problem is $\Omega(n \log n)$?
how to prove that the lower bound of the Huffman coding problem is $\Omega(n \log n)$?
Here Huffman coding problem is Huffman encoding.
For example,
...
- 165
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
217
views
Lower bound on comparison-based sorting
I have a question from one of the exercises in CLRS.
Show that there is no comparison sort whose running time is linear for at least half
of the $n!$ inputs of length $n$. What about a fraction of $1/...
- 23
0
votes
1
answer
468
views
0
votes
2
answers
2k
views
Lower bound and worst case scenario
We know that the lower bound is the minimum amount of work needed to solve a problem. So for a given problem say x it has the best algorithm ( the most efficient algorithm to solve this problem ) say ...
- 13
2
votes
0
answers
99
views
Decision Tree for searching an element in an n*n matrix
I just learnt decision tree concept in class. I have a question for homework. It says to prove that for searching an element in n*n matrix the lower bound is logn and prove it using decision tree.
My ...
- 21
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
3
votes
1
answer
71
views
Finding maximum takes at least $\lceil n/2 \rceil$ comparisons
We are given an array $A$ with $n$ elements, $n \in \mathbb{N}$ and all elements are in the set $\{1,2,3, \cdots, n \}$.
I want to prove that finding the maximum in $A$ (that is, outputting the index ...
- 33