Algorithm exercise

Question

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 How to ask and answer homework questions? and it seems to be possible to make these kind of question.

Thanks in advance.

Answer 1

$\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.