Member Avatar for apaciboy

Hi
I need a solution for this problem,please help me..

It is a table with sorting elements, where n = i x j. We separate the table in i subtables with j elements each one. In order to search a key first of all we compare each one with the last key of each subtable. With this way we understand in which subtable we continue to seach. In the event successful search, at worst will be executed i + j comparisons, in the medium case will be executed i+1/2 + i+1/2 comparisons. For which prices the i, j record is optimised?

  • 2 Contributors
  • 3 Replies
  • 145 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by Murtan
Member Avatar for Murtan

I think I understand your data structure from your description.

I think I understand how you search it.

I think I can agree with your premise for the worst case search. I think the math for your average case should be i/2 + j/2.

However, I don't think I understand your last question. You seem to be asking something about a 'best case' but I don't understand what you are asking for.

Member Avatar for apaciboy

hi murtan

i asked as you say about the best case prices for the keys i and j..
i wait your answer..thanks

Member Avatar for Murtan

I think it would depend a on how you search the subtables.

From your description, I'm presuming that the data in the subtables are ordered and that the subtables are in order as well.

You described the search to find the correct subtable: sequential search through the highest value in the subtable until you find one higher than what you're looking for.

You didn't describe the search through the subtables, but for the sake of argument I will presume that it is also a sequential search through the subtable from smallest to largest.

So the most optimally found value (2 compares) is the lowest value in the collection.

The worst case (i + j) would be the highest value in the collection.

Everything else is somewhere in between.

Is that what you were trying to ask?
So if the search algorithim is a sequential search across the highest key in the subtable (until you find one higher than the value you're looking for).

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.