0
$\begingroup$

I have done an assignment question which asks me to find the average case of pentary search. The one I came up with is:

C(n) = C(n/5) + 14/5

However, I got it wrong and the professor didn't really explain why.

Can you help me?

Thanks!

Edit:

Pentary search is dividing the array into 5 parts and look for a specific key.

In perspective:

1|2|3|4|4

These are the number of comparisons made by the computer from pentary search.

Adding all possible comparisons I get 14 over 5 slots. This is why I have 14/5

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ I think a minimal explanation (i.e. "what is pentary search") might help. $\endgroup$ – G. Bach Oct 14 '13 at 0:38
  • $\begingroup$ Edited, sorry about that $\endgroup$ – Julio Garcia Oct 14 '13 at 0:43
1
$\begingroup$

There is at least one thing that could be wrong with your recurrence, depending on how exactly the algorithm is stated: you are overlooking the case that the element could be found before recursion.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 1. That makes sense. 2. So is it 14/4? $\endgroup$ – Julio Garcia Oct 14 '13 at 2:20
  • $\begingroup$ I get something else. Don't guess, compute the average number of comparisons. You can use the formula for expectation if you're not sure how to. $\endgroup$ – Yuval Filmus Oct 14 '13 at 2:34
  • $\begingroup$ Hmm, that'll be tricky. I left an explanation as to why I got 14/5 as an edit. $\endgroup$ – Julio Garcia Oct 14 '13 at 2:38
  • $\begingroup$ Ok, I guess you're right and I made a mistake... (The previous version of my answer erroneously claimed that the average number of comparisons has to be of the form $X/4$ instead of $X/5$.) $\endgroup$ – Yuval Filmus Oct 14 '13 at 2:39
  • $\begingroup$ I'm right on the edit or the second previous comment? $\endgroup$ – Julio Garcia Oct 14 '13 at 2:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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