Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Example

We wish to implement a searchable container which will be used to contain character strings from the set of strings K,

equation11142

Suppose we define a function tex2html_wrap_inline62140 as given by the following table:

x h(x)
"ett" 1
"två" 2
"tre" 3
"fyra" 4
"fem" 5
"sex" 6
"sju" 7
"åtta" 8
"nio" 9
"tio" 10
"elva" 11
"tolv" 12

Then, we can implement a searchable container using an array of length n=12. To insert item x, we simply store it a position h(x)-1 of the array. Similarly, to locate item x, we simply check to see if it is found at position h(x)-1. If the function tex2html_wrap_inline59195 can be evaluated in constant time, then the both the insert and the find operations are O(1).

We expect that any reasonable implementation of the function tex2html_wrap_inline59195 will run in constant time, since the size of the set of strings, K, is a constant! This example illustrates how we can achieve O(1) performance in the worst case when we have complete, a priori knowledge.

next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.