The benchmark registered by BENCHMARK(BM_Complexity_O1) -> Range(1, 1<<18) -> Complexity(); sometimes reports it's complexity as lgN as opposed to ([0-9]+). This happens when one of the later repetitions happens to run faster due to CPU load.

For example:

BM_Complexity_O1/1                 2106 ns       3125 ns      10000
BM_Complexity_O1/8                 2132 ns       1563 ns      10000
BM_Complexity_O1/64                2050 ns       3125 ns      10000
BM_Complexity_O1/512               2032 ns       1563 ns      10000
BM_Complexity_O1/4k                2041 ns       1563 ns      10000
BM_Complexity_O1/32k               2264 ns      15625 ns       1000
BM_Complexity_O1/256k              2128 ns       1563 ns      10000
BM_Complexity_O1_BigO            163.31 lgN     389.19 lgN 

I'm not quite sure how to fix this test, or even if this is a bug in the complexity implementation. I would like some guidance on how to tackle this.

This is making our Appveyor build frequently fail so I would like to fix it. For now I'm going to checkin a temporary fix which simply accepts 'lg(N)' as valid test output.