Probabilities in Complexity of Sequential Search Question
- From: "eKo1" <berndlosert@xxxxxxxxxxxx>
- Date: 30 Dec 2006 23:01:21 -0800
Question: What is the average complexity of sequential search if there
is a 0.25 chance that the target will not be found in the list and
there is 0.75 chance that when the target is in the list, it will be
found in the first half of the list?
I don't understand this problem very well. It seems to suggest that the
probability that the target is in the second half of the list is 0. The
book where I got this problem says that the average case time is given
by the following formula:
A(n) = sum(i=1 to m) p_i t_i
where n is the size of the input, m is the number of groups into which
all possible input sets can be divided, p_i is the probability that the
input will be from group i, and t_i is the time that the algorithm
takes for input from group i.
I suppose there are n + 1 groups: group i being when the target is the
ith item in the list, i = 1 to n, and group n + 1 being when the target
is not in the list. t_i = i for i = 1 to n. t_(n+1) = n. If n is even,
then
A(n) = 0.75 sum(i=1 to n/2) i + 0 sum (i=n/2+1 to n) i + 0.25 n = 3/32
n(n+2) + 1/4 n = O(n^2)
What do you think?
.
- Prev by Date: passive radar theory refrence needed
- Previous by thread: passive radar theory refrence needed
- Index(es):
Relevant Pages
|
