Testing for an empty dictionary in Python

[John Machin]

On Mar 24, 2:53 am, John Nagle <na... at animats.com> wrote:
>    What's the cheapest way to test for an empty dictionary in Python?
>
>         if len(dict.keys() > 0) :

TypeError: object of type 'bool' has no len()

I presume you meant
    if len(dict.keys()) > 0:

>
> is expensive for large dictionaries, and makes loops O(N^2).

I don't understand "makes loops O(N^2)" ... what I see in the
dict_keys function in Objects/dictobject.c is that it makes one linear
pass through its table, ignoring unused and formerly-used slots; seems
like O(N) where N is the size of the table. Where did you get O(N^2)
from?