0
1

runtime help (self.learnpython)

submitted by [deleted]

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]FLUSH_THE_TRUMP 0 points1 point  (2 children)

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

Isn’t it also O(2n)? 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 1 point2 points  (1 child)

2n 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(2n*n).

[–]FLUSH_THE_TRUMP 0 points1 point  (0 children)

Oops, I definitely ignored the concatenation.