Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 and it seems to be possible to make these kind of question.

Thanks in advance.

share|cite|improve this question

migrated from Nov 27 '12 at 19:06

This question came from our site for theoretical computer scientists and researchers in related fields.

Is that the whole question? What kind of search and decision tree is it talking about? It would help if you posted something to show you've tried to solve the problem yourself. Do you have any ideas and why it might be the right answer, or did you think another answer is correct? – fgb Nov 27 '12 at 16:49
the quesion is all there, there's not written about any specific tree, the problem is to understand the question and what does it mean, for example if I have N elements, are not the leafs N+1 for not found? – newbie Nov 27 '12 at 17:16
Which answer is associated with which question? – Joe Nov 27 '12 at 20:39
both answers 1. and 2. are associated to the first question – newbie Nov 27 '12 at 20:56
up vote 1 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.