It’s Time Again

Consider the time-complexity (i.e., running time) of various operations in CPython, the interpreter installed in CS50 IDE, focusing exclusively on each operation’s Average Case.

Answer the below in time.txt.

Questions

  1. (2 points.) Recall that a dict is essentially a hash table, most of whose operations are in O(1). And yet Copy is in O(n). Why?

  2. (2 points.) Recall that, for Sentiments in Problem Set 6, you had to load positive and negative words into memory. Why would a set have been a better choice than a list for those words?

  3. (2 points.) Recall that strlen is in O(n) for strings in C. Though not documented, it turns out that len is in O(1) for strings in Python. How could that be?

Debrief

  1. Which resources, if any, did you find helpful in answering this problem’s questions?

  2. About how long did you spend on this problem’s questions?