[Python] Is capping `max_element` reasonable when testing an O(2^n) subset sum solver?

I am using this (among other) instance generators to test a subset sum solver. The solver is n-dependent only, with time complexity O(2^n).

I capped the max_element size at 2**22 because I noticed that when I go above, say, 2**30, it massively slows down on my cheap laptop.

I am using values of n up to 512 (though I’m currently achieving sub-second runtimes at around n = 128).

My question is:
Given the O(2^n) dependence, is this kind of max_element cap reasonable for evaluating the algorithm’s performance — as distinct from the machine’s performance?

I’m posting here because I believe this is a theoretical, algorithmic, and implementation-related question that falls under this site’s scope. If I’ve misjudged that, I apologize in advance.

import random

def generate_exponential_instance(n):
max_element = 2 ** 22
A = [random.randint(1, max_element) for _ in range(n)]

while True:
mask = [random.choice([0, 1]) for _ in range(n)]
if sum(mask) != 0:
break

target = sum(A * mask for i in range(n))
return A, target

Continue reading...