Suppose you want to design a dictionary class, D
, using a stack class, S
, as your underlying structure. (Perhaps you are working in a restricted environment.)
You may assume S.push(pointer)
, S.pop()
, and S.isEmpty()
in \( \mathcal{O}(1) \) time, you may make \( \mathcal{O}(1) \) stacks, and you need not worry about overflow.
What would be the asymptotic worst-case complexity of your D.Search(key)
, D.Insert(pointer)
, D.Delete(pointer)
, D.Successor(pointer)
, D.Predecessor(pointer)
, D.Minimum()
, and D.Maximum()
?
(Given a pointer to an object you can access that object's key.)
Given n
points in three dimensions, e.g. [(1,2,3), (6,5,4)]
, design an algorithm which finds the closest two. What is the complexity of your approach?