Searching elements a sorted compact list
a. Consider that COMPACT-LIST-SEARCH 
(refer
textbook, problem 10-3) takes 
iteration
of “while” loop of line 2-8
Now depending on value of
, there are
two cases:
1. is in
list
2. does not
exist in the list
Case1: is stored in
the list
Since is there in
the loop, therefore, COMPACT-LIST-SEARCH will take
iterations
and return the object. COMPACT-LIST-SEARCH’
will do the
same in the ‘for’ loop of line 2-7. It may has to do one more
iteration of the while loop hence total iterations are more
than.
Case2: is not in
the list
In this case COMPACT-LIST-SEARCHwill get
=NIL or no
less than in
iteration. COMPACT-LIST-SEARCH’ will get
the same in at least iteration
since while loop will add more iteration.
Hence, conclusion is that COMPACT-LIST-SEARCH’ would yield
an answer same as that of COMPACT-LIST-SEARCH and total
number of iterations done in both of them ‘for’ and ‘while’ loops
within COMPACT-LIST-SEARCH’ would be at least.
b. Procedure COMPACT-LIST-SEARCH’ is
comprised of two loops,
1. ‘for’ loop from line 2 to 7. Assume that it takes 
2. ‘while’ loop from line 8 to 9. Assume that it takes 
3. Rest of the line can be executed in constant time.
So it will take
.
Therefore from 1, 2 and 3, total time will be:
… … (1)
Calculation of 1,
Since for loop runs for t time doing a constant work each
time, therefore total time in executing this loop will be
.
That is
.
Therefore,
… … (2)
Calculation of 2,
After
iterations i will at a distance of
to the desired key .
Therefore,
It will get the expectation as
. In other
word, implication is that there is while loop which will run
times, each time doing a constant work.
Therefore total running time of this while loop will be
… … (3)
Putting the values got in equation (2) and (3) in (1)
Equation comes as,
So above explanation conclude that expected running time of
COMPACT-LIST-SEACH’ is
c. 
is defined
in section C.3 of the text book (equation (C.25)) as following:
In present scenario, the above equation could be as below,
… … (4)
Probability of 
is
equivalent to the probability
,
probability 
…...
probability
Each of these will have a maximum possibility of
.
Therefore, probability of getting will always
be greater than or equal to
.
Therefore it can be rewritten equation (4) as bellow,
d.
Consider the following:
… … (5)
(It is quite obvious to observe that 
is
summation just over the integral part on the other hand 
is summation
over fraction also.
Therefore,
Will always
be greater or equal to)
… … (6)
Now, consider the below inequality expression,
… … (7)
From (6) and (7),
… … (8)
From (5) and (8),
e .
From part c,
… … (9)
Now, changing the limit,
… … (10)
From the part d,
… … (11)
Substituting the value of (11) in (10)
Or, 
Or
… …
(12)
From equation (9) and (12),
Hence proved
f.
In part b, it is already shown that expected running time
of COMPACT-LIST-SEARCH’ is
… … (13)
In part e already proved that
.
Substituting the value of in equation
(13)
=
=
=
g.
Since COMPACT-LIST-SEARCH has same running for and while loop, its running time will be same as that of COMPACT-LIST-SEARCH.
Hence,
Running time of COMPACT-LIST-SEARCH=
Now out of and
,
One having bigger value will dominate the total running time.
Assuming that
Hence,
Or
… …
(14)
Since running time of COMPACT-LIST-SEARCH=,
Therefore substituting the value of form
equation (14)
=
=
=
=
h.
Assumed no two keys in COMPACT-LIST-SEARCH are same, so that
skip performed by RANDOM
has more
significance.
Consider that there are duplicate keys in the list. In that case
when the skip is performed by RANDOM, the worst
case possibility is that the next key that is accessed is same as
the key from which the skip was performed.
Now, the next thing to do would be that the while loop has to move the pointer backward step by step. If this happens, the skip does not come in handy and cannot fulfill the need that it was meant for.
So when the lists are created, it is taken care of that all the keys are different.