Average Case Analysis for algorithm that searches in array

I have to do a Average Case Analysis for an algorithm that searches an integer K in an array.

Assume that every element in the n-element array shows up exactly twice (so there are n/2 distinct values, and each value occurs in two separate places in the array). Assume the array is unsorted (so the elements are 'randomly scattered' throughout the array).

I have to develop a formula for A(n), in terms of n and q(n is the number of elements in the array).

Thank you.

If I understand what you're saying, then (example) in a 4by4 array, the numbers
1 to 8 would each be entered twice completely at random, to possibly look like:
6 5 1 2
4 7 7 8
8 6 1 3
3 2 4 5

Then one number is to be searched for: only needs to be found once, not twice.

And you are trying to devise an "efficient" way of doing this search?

Can there be a 5th column in the array, to be used as totals for each row:
6 5 1 2 14
4 7 7 8 26
8 6 1 3 18
3 2 4 5 14
These totals would be "calculated" during the initial job, where the numbers
are randomly assigned their rooms for the night...

Denis, I don't see how the extra column helps, but senility has kicked in.
I don't think there is any way better than just going thru the list, one at a time, checking for a match.
I can't derive the average case formula (senility again) but the answers for 1 to 10 pairs seems to be
n - p
1 - 1
2 - 5/3
3 - 7/3
4 - 3
5 - 11/3
6 - 13/3
7 - 5
8 - 17/3
9 - 19/3
10 - 7
which implies it is (2n+1)/3 where n is the number of pairs and p is the average number of checks.
--------------------------
I hope this helps.

Since the search is not at random, then it can be row by row,
while totalling the elements:

4 7 7 8 26

If search is for 8, then you can stop at 2nd 7, saving one look;
26 - 4 - 7 - 7 = 8

8 6 1 3 18

If search is for 7, then you can stop at the 6, saving 2 looks:
18 - 8 - 6 = 4 (so 7 impossible)

That was my thinking, Gene; makes no sense :?:

Hmmm, I see where you were going now but I'd have to look at the assembly code. I would suspect that the math would use up more cycles that it would save. Wouldn't you have to "look" at each non-match once to see if it was a match then again to use it in the subtraction, then another compare to test the remainder?
I couldn't even begin to come up with a formula for that.
-----------------
Gene

This guy's problem is not too clear; does not specify HOW the search is made:
like, is it a random search? The he throws in "q" with no explanation.

Anyway, if you search an array at random or orderly, time should come out
to be the same on average.

I approached the problem like this:
1: an array has to be searched for a number
2: each number appears twice in the array
3: the array has been randomly filled
4: totals in each row are available

Doing it the way I describe (orderly, get out if out-of-range!) takes
close to 4.5 "looks" to find the number: ~4.43 in a simulation of a million;
that's with the 4by4 array I talked about.

Now, if searching at random takes say 8 looks, I don't know which would
quickest; the random search will not require the arithmetic; but some
time will be used up to somehow ensure a random look is not in the same
"spot" as one already looked at...

Anyhoo, who cares :twisted:

Looked at this again, with the array searched with no help like row totals;
in other words, same as searching a 1 row array.
With n = array size (n = 16 if 1 to 8 are the numbers):
n : looks
4 : 1 2/3
6 : 2 1/3
8 : 3
10:3 2/3
12:4 1/3
14:5
16:5 2/3
18:6 1/3
20:7
and so on...

Formula: (n + 1) / 3 ; if n=16: 17/3 = 5 2/3

Has to do with the sum of triangular numbers; example, if n=4:
1 1 2 2
1 2 1 2
1 2 2 1
2 1 1 2
2 1 2 1
2 2 1 1

Take the "1": 1st 3 times, 2nd twice, 3rd once (4th once don't matter).
1+1+1+2+2+3 = 10 ; 10 / 6 = 1 2/3

Similarly for others; if n=6:
1+1+1+1+1+2+2+2+2+3+3+3+4+4+5 = 35; 35 / 15 = 2 1/3

I don't care to elaborate :shock: