In the course material, there is an example for week 4 of an algorithm using a dictionary for counting the rounds needed to collect numbers from a list. Earlier in an exercise for week 2, the same task was solved using a list instead of a dictionary.
The auxiliary data structure used in the task can be either a list or a dictionary, because a number can be used either as a list index or as a dictionary key. How does the choice of the data structure affect the efficiency of the algorithm?
Compare the efficiency of the two implementations for an input list containing the numbers 1,2,…,107 in a random order.
In this task you get a point automatically, when you fill in your results and the code you used, and press the submit button.
Running time when using a list: s
Running time when using a dictionary: s
The code used in the test:
