Chapter 2, Building Abstractions with Data

Section - 2.3 Symbolic Data

Exercise 2.72

We need to look at maximum of levels.

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

Worst case time in a search for symbols is .

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

Since 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 will be the time to lookup in a step where 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 symbols.

In second, we shall lookup in symbols.

and so on.

Thus total complexity should be:

Thus average complexity shall be .