"In computer science, big O notation is used to classify algorithms according to how their running time or space requirements grow as the input size grows" - https://en.wikipedia.org/wiki/Big_O_notation

It does not refer to the number of high-level execution frames, which appears to be what you measured.

Consider that in Python:

   a = []
   for i in range(500_000):
     a.append(i)
   a.reverse()

takes about 0.1 seconds, while

   a = []
   for i in range(500_000):
     a.insert(0, i)

takes about a minute, to produce the same result. That's a factor of 600, even though the first one actually executes more Python code.

This is because the first uses an amortized O(N) method, while the second uses an O(N^2) method.

Hence, you need to measure run time, not the number of frames.

I don't need to try it out because you wrote "every possible set of values for the boolean variables will be in memory", which requires O(2^N) values for the worst case, which require O(2^N) for the CPU to touch each memory cell.

Also, try something with 10,000+ variables. Or one of the benchmark test sets from http://www.satcompetition.org/ .