Sigh, the time bound here requires explaining. It's O(N) where N is the number of edges. It's O(N^2) where N is the number of blocks (vertices). (In a comple

Sigh, the time bound here requires explaining. It's O(N) where N is the number of edges. It's O(N^2) where N is the number of blocks (vertices). (In a complete graph of N vertices, there are N^2 edges) Papers switch between the two (elimination based methods are often in terms of edges, non-elimination in terms of number of blocks) Also, if you read papers from these days, bitvector operations are considered to take constant time. (see footnote 2 in https://core.ac.uk/download/pdf/82093362.pdf https://core.ac.uk/download/pdf/82093362.pdf). They do in fact take constant time if they are constant size independent of program, but they are often not. They are usually linear in the number of variables/blocks. For those linear in the number of blocks, the total time bound comes to N^3 (and N^2 log N for a class of problems). For those linear in the number of variables O(V*N^2). For those constant sized, the time bounds are correct since the operations take constant time. (and FWIW: This group of people has probably forgotten more about program analysis than the rest of us will ever know)