BACKGROUND INFORMATION

The Bibliography Abstract Data Type stores references. References can be added to the bibliography or removed from the bibliography. No matter how references are represented, they are ordered. Duplicate references are not allowed. You can assume that each author has just one publication and that each publication has only one author.

The ADT for a Bibliography includes these operations:

• new, which creates a new, empty bibliography
• addReference, which adds a reference to the bibliography
• removeReference, which removes a reference from the bibliography
• outputBibliography, which generates an ordered list of references

QUESTION

For this part, how a reference is represented doesnt matter. The following stand-alone Python function accepts a list of references and returns a bibliography containing those references. It assumes the ADT is implemented as a Python class, i.e. using Bibliography() as the new operation.

def makeBib(ref_list):

myBib = Bibliography()

for ref in ref_list:

myBib.addReference(ref)

return myBib

What is the best-case Big-O complexity of the makeBib function for an input list with n references? Explain your answer. Take each Bibliography operation as a basic step of computation.

Holden, G Cripps, s Xavier, 1 Brown, D Ferret, Hominid, P Krowley, J