big o - Time Complexity Python Script -

i writing small script guesses numeric passwords (including ones leading zeros). script works fine having trouble understanding worst case time complexity algorithm. insight on complexity of implementation great, thanks.

def bruteforce(ciphertext):     plen in itertools.count():         password in itertools.product("0123456789", repeat=plen):             if hashlib.sha256("".join(password)).hexdigest() == ciphertext:                 return "".join(password) 

first, it's possible you're going find hash collision before find right password. and, long-enough input string, guaranteed. so, really, algorithm constant time: complete in 2^256 steps no matter input is.

but isn't helpful when you're asking how scales more reasonable n, let's assume had upper limit low enough hash collisions weren't relevant.

now, if password length n, outer loop run n times.*

_{* i'm assuming here password will purely numeric. otherwise, of course, it'll fail find right answer @ n , keep going until finds hash collision.}

how long inner loop take? well, main thing iterate each element in product("0123456789", repeat=plen). iterates cartesian product of 10-element list plen times—in other words, there 10^plen elements in product.

since 10**plen greater sum(10**i in range(plen)) (e.g., 100000 > 11111), can ignore last time through outer loop, 10**plen total number of inner loops.

the stuff inside each inner loop linear on plen (joining string, hashing string) or constant (comparing 2 hashes), there (10^plen)*plen total steps.

so, worst-case complexity exponential: o(10^n). because that's same multiplying n constant , doing 2^cn, that's same complexity class o(2^n).

if want combine 2 together, call o(2^min(log2(10)*n, 256)). which, again, constant-time (since asymptote still 2^256), shows how it's practically exponential if care smaller n.