[Solved]: Algorithm exercise

Problem Detail: 

making exercises to prepare a test I'm having problems to understand 2 questions, the questions are:

 how many are the leafs of a decisional tree associated to any algorithm for    the search problem  in a ordered set? 

for this question I have 2 set of answer where, for every set, 1 is right, looking at the solution I found this, but I'm not able to understand why the right answers are all C.

    1.                 a) Θ(n log n)    b) Θ(log n) *c) Ω(n!)   d) O(n!)      2.                 a) Θ(n log n)    b) Θ(log n) *c) Ω(n)    d) Θ(n!) 

The other question, referred to the first one is:

  and in a non-ordered one? 

And here I can't see what does it change with the number of leafs in the ordered case.

I'm sorry if this question violates the rules, in the faqs, I read here http://meta.stackexchange.com/questions/10811/how-to-ask-and-answer-homework-questions and it seems to be possible to make these kind of question.

Thanks in advance.

Asked By : newbie

Answered By : Joe

$\Omega(n!)$ is not a reasonable answer. The decision tree for the search problem on the ordered set is just a binary search tree. It has $\Theta(n)$ leaves. Unless they mean something non-standard by "search problem" and "decision tree". These arguments in terms of number of leaves in the decision tree are typically used in lower bound arguments. Wikipedia has an (incomplete) discussion of the decision tree model.

In the unordered case, the decision tree still has $\Theta(n)$ leaves, using linear search.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6961

 Ask a Question

 Download Related Notes/Documents