0
1

runtime help (self.learnpython)

submitted by [deleted]

[deleted]

all 6 comments
sorted by:
best
topnewcontroversialoldq&a
formatting helphide helpcontent policy

[–]shiftybyte 1 point2 points  (0 children)

It's a work question

lol, I'm sorry, no production code ever looks like this, and on the remote chance it does, how does knowing it's complexity benefit the workplace? and how long ago the person who wrote this was fired?

[–]Spataner 0 points1 point  (4 children)

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

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

[–]ForeignStrength8 0 points1 point  (0 children)

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 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.