# 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

• 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