# Pentary Search Recurrence Relation

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

• I think a minimal explanation (i.e. "what is pentary search") might help. – G. Bach Oct 14 '13 at 0:38
• Edited, sorry about that – Julio Garcia Oct 14 '13 at 0:43

## 1 Answer

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.

• 1. That makes sense. 2. So is it 14/4? – Julio Garcia Oct 14 '13 at 2:20
• 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. – Yuval Filmus Oct 14 '13 at 2:34
• Hmm, that'll be tricky. I left an explanation as to why I got 14/5 as an edit. – Julio Garcia Oct 14 '13 at 2:38
• 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$.) – Yuval Filmus Oct 14 '13 at 2:39
• I'm right on the edit or the second previous comment? – Julio Garcia Oct 14 '13 at 2:40