Recall that a dict is essentially a hash table most of whose

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? 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?

Solution

1) dict contains N elements. So to duplicate whole table, we need to traverse each item at least once. There are N items thats why the complexity of copy is O(n).

2) In C to calculate string length, we traverse the string buffer and count each occupied char but in python instead a variable is stored in string object that keeps track of string length. So when len is queried, it just looks up from that temporay variable(__len__ method) and returns instead of counting each char buffer.