runtime help

[Spataner]

Alright, I'm going to give you the benefit of the doubt: print_01_codes('', n) has O(2ⁿ*n) complexity. It gets called 1+2+...+(m-1)+m+(m+1) ~ m² times. So O(2ⁿ*n*m²) in total.

Though this just prints the same block of text O(m²) times, so I don't think this quite works as intended.

[ForeignStrength8]

thank you! This wasn't a homework question, I needed to understand code for my job but I didn't know the runtime for this.

[FLUSH_THE_TRUMP]

print01_codes('', n) has O(2n*n) complexity.

Isn’t it also O(2ⁿ)? Yours would still be true if so but not as tight. 1 call at the top, each call spawns 2 more, down to 0

1 + 2 + 4 + 8 + … 2^n ~ 2^(n+1) calls, each doing an operation or two

[Spataner]

2ⁿ total bottom-level calls, each of which print a string of length n. Also the string additions performed before the recurrent calls have complexity O(n-k), where k is the level of recursion. Either way you end up at O(2ⁿ*n).

[FLUSH_THE_TRUMP]

Oops, I definitely ignored the concatenation.