Chapter 2, Building Abstractions with Data

Section - 2.3 Symbolic Data

Exercise 2.72

We need to look at maximum of $n$ levels.

At each level we search in ordered set of symbols. Also at first node we search in $n$ symbols then we search in $n/2$ symbols and so on.

Worst case time in a search for $k$ symbols is $k$.

If an element is not found in left branch, we look for it in right branch. Thus total search time in this case is $n + n = 2n$.

Since $n$ is worst case search time as well as on average we shall only be looking in only left branch half of the time.

On average we can say that $2n/2 = n$ will be the time to lookup in a step where $n$ is the number of symbols present in left or right node(assuming they will be equal).

Each time when a branch is selected, number of symbols in branch are reduced by half.

Thus in first step we shall be looking in $n$ symbols.

In second, we shall lookup in $n/2$ symbols.

and so on.

Thus total complexity should be:
$= n + n/2 + (n/2)/2 + ((n/2)/2)/2 ... 1$
$= n(1 + 1/2 + 1/4 + 1/8 + 1/(2^{\log n})$
$= n \times \frac { 1 - {(1/2)}^{\log n} } { 1 - 1/2 }$
$= 2 \times n \times ( { 1 - {(1/2)}^{\log n} } )$
$= 2 \times n \times ( 1 - 1/n )$
$= 2 \times n \times ( (n - 1)/n )$
$= 2 \times (n - 1)$

Thus average complexity shall be $O(2n)$.