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.