Suppose that your symbol table implementation supports the insert and search ope

Question

Suppose that your symbol table implementation supports the insert and search operations in amortized 4 log N compares. Which of the following are true?

I. Starting from an empty data structure, any sequence of N insert and search operations uses at most 4N log N compares.  
II. Any sequence of N insert and search operations uses at most 4N log N compares.
III. Starting from an empty data structure, the expected number of compares to perform N insert and search operations is 4N log N , but there is a (small) probability that it will take 5N log N compares (or more).

A. I, II and III

B.

I only

C. II or III

D. I and II only

E. None of these

F. I and III only

Explanation / Answer

B. I only

Amortized analysis will provides a worst-case guarantee on any of the sequence of operations starting from an empty data structure.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.