3.9.1 Analysis of Expected Search Cost

We analyze the search path backwards, traveling up and to the left. We pretend as if the level of a node is being determined only when it is observed while backtracking the search path.

1.

From level 1, we rise to level L(n)

2.

We move leftward

3.

We climb from L(n) to maxLevel.

At a particular point in the climb, we are at the i^th forward pointer of a node x and we have no knowledge about the levels of nodes to the left of x or about the level of x (other than that the level of x must be $\geq$i ). See situation (a) in figure.

• Assume ``x'' is not the header.
• If level of x is i, then we are in situation (b). If level of x is > i, we are in situation (c).
• Prob{ we are in situation cA} = p
• Each time we are in situation c, we climb up one level.

Let  

C(k) =	expected length of a search path that
	.climbs up k levels in an infinite list.

Then:  

C(0) =	0
C(k) =	p  {cost in situation c }
	(1 - p)  { cost in situation b }

We get
 

C(k) =	p  {1 + C(k - 1)} + (1 - p){1 + C(k)}
C(k) =	$${\frac{1}{p}}$$ + C(k - 1)
C(k) =	$${\frac{k}{p}}$$

Our assumption that the list is infinite is pessimistic.

When we bump into the header in our backward climb, we simply climb it up without performing any leftward (horizontal) movements.

This gives us an upperbound of 

$$\left(\vphantom{ \frac{L(n) - 1}{p} }\right.$$$${\frac{L(n) - 1}{p}}$$$$\left.\vphantom{ \frac{L(n) - 1}{p} }\right)$$ On the expected length of a path that climbs up from level 1 to level L(n) in a list of n elements. (because L(n) - 1 level are being climbed).

The rest of the journey includes

1.

leftward movements, the number of which is bounded by the number of elements of level L(n)or higher. his has an expected value = ${\frac{1}{p}}$

2.

We also move upwards from level L(n) to the maximum level in the list. 

 

p  {   maximum level in the list	> k}
	= 1 - (1 - pk)n
	$$\leq$$npk

 

p  { $$\mbox{ an element has a level $> k$ }$$}	= pk
$\Longrightarrow$p  { $$\mbox{ an element has level$\leq \; k$ }$$}	= 1 - pk
$\Longrightarrow$p  { $$\mbox{ all $n$\space elements have level$\leq \; k$ }$$}	= (1 - pk)n
$\Longrightarrow$p  { $$\mbox{ at least one element has level$ \geq k$ }$$}	= 1 - (1 - pk)n
Expected maximum level	$$\leq$$npk
$\Longrightarrow$   Expected maximum level	$$\leq$$L(n) + $${\frac{1}{1-p}}$$

Putting our results together, we get:

Total expected cost to climb out of a list on n elements

$\leq$${\frac{L(n)}{p}}$ + ${\frac{1}{p}}$ which is O(log n).

We can also compute the probability if the actual cost of a search exceeds expected cost by more than a specified ratio.

Examples

1.

     p = ${\frac{1}{2}}$;    n = 256

p  {search will take longer than 3 times the expected cost  } = $\overline{10}^{6}_{}$

2.

     p = ${\frac{1}{2}}$;    n = 4096

p  {search will take longer than 2 times the expected cost  } = $\overline{10}^{4}_{}$

3.

     p = ${\frac{1}{2}}$;    n = 1024

p  {search will take longer than 3 times  } = $\overline{10}^{18}_{}$

How do we choose p ?

• Decreasing p increases variability of running times.
• p = ${\frac{1}{2}}$ ; generation of random level can be done from a stream of random bits.
• Decreasing p decreases # of pointers per node.
• Overheads are related to L(n) rather than ${\frac{L(n)}{p}}$.
• p = ${\frac{1}{4}}$ is probably the best choice, unless variability of running times is an issue.