Question

Present the running time (in terms of Big-Oh notation) of the operations search, insert, delete, print all elements, find median, find min/max, successor while implementing a dictionary ADT using (1) Unsorted arrays (2) sorted arrays (3) Balanced BST.

Answer 1

1) Unsorted arrays:

• insert -> O(1)
• delete -> O(n)
• print -> O(n)
• median -> O(n log n)
• finding min/max -> O(n)
• search -> O(n)
• successor -> O(n)

2) Sorted arrays:

• insert -> O(n)
• delete -> O(n)
• print -> O(n)
• median -> O(1)
• finding min/max -> O(1)
• search -> O(log n)
• successor -> O(log n)

3) Balanced BST:

• insert -> O(log n)
• delete -> O(log n)
• print -> O(n)
• median -> O(n)
• finding min/max -> O(log n)
• search -> O(log n)
• successor -> O(log n)