Hello, I am trying to teach myself algorithms (Sedgewick) and have encountered the following problem:

```
3.1.15: Assume that searches are 1,000 times more frequent
than insertions for a BinarySearchST client. Estimate the
percentage of the total time that is devoted to insertions,
when the number of searches is 10^3, 10^6, and 10^9.
```

As stated in the problem Search queries (S) = 1000 * Supplements (I)

- $ S = 10 ^ 3 to I = 1 $
- $ S = 10 ^ 6 to I = 10 ^ 3 $
- $ S = 10 ^ 9 to I = 10 ^ 6 $

At this point in the book, we use simple arrays and linked lists to back up the symbol table (inefficient hash maps, trees, and so on). This would mean that the search takes ~ log2 (N) and the insertion takes ~ N / 2 times (assuming a uniform distribution where the inserts are placed).

Is the calculation of the percentage of insertion for the search time approximately:

$ frac {Inserts times N / 2} {Searches times log_2 (N)} $

Use $ Searches = 10 ^ 3 times Inserts $ that reduces to

$ frac {N / 2} {(10 ^ 3 times log_2 (N)} $

This would mean that the percentage is heavily dependent on the initial size of the symbol table and is not a steady percentage that we can use to answer the question.

Are there suggestions for what I missed? Should I make a guess about the initial size of the table?