Hi I'm attempting to self teach myself from Algorithms (Sedgewick) and ran across 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 Searches (S) = 1000 * Inserts (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 are using simple arrays and linked lists to back symbol table (not efficient hash maps, trees, etc). This would mean searches take ~log2(N) time and insertions take ~N/2 time (assuming a uniform distribution on where inserts are placed).

Am I correct in calculating the % of insert to search time would approximately be:

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

Using $Searches = 10^3 \times Inserts$ this reduces to

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

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

Any suggestions for what I am overlooking, should I be making an assumption about the initial size of the table?


In computation, time consume depends deeply on the algorithm we choose. Since the search time consumes log2(N) and insertion time consumes N/2, the insertion time increases sharply as compared to the search time. The only thing is that they depend on size of the symbol table, not the initial size because insertion and search time depend on the actual size of data set.

The chart below shows Percentage of Insertion Time over Search Time in your case.

enter image description here

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.