# Is the time complexity of this function O(n^3)? And O(n) for its memoized solution?

Given this naive recursive function:

def largest_tower(heights_and_widths, prev_height=1000, prev_width=1000):
if not heights_and_widths:
return 0

results = {0}

for i in range(len(heights_and_widths)):
current_height, current_width = heights_and_widths[i]

if current_height < prev_height and current_width < prev_width:
subarray = heights_and_widths[:i] + heights_and_widths[i+1:]

return max(results)


At first sight, I would have said that the time complexity of this function is O(n^2). But, if I'm not wrong, explained in plain words would be: This function may call itself (n-1) + (n-2) + ... + 1 times, being that O(n^2), but a total of n times, so the actual time complexity is O(n^3). Am I right?

And for the memoized version:

def largest_tower_memoized(heights_and_widths, prev_height=1000, prev_width=1000, cache=None):
if not heights_and_widths:
return 0

if cache is None:
cache = {}

results = {0}

for i in range(len(heights_and_widths)):
current_height, current_width = heights_and_widths[i]

if current_height < prev_height and current_width < prev_width:
subarray = tuple(heights_and_widths[:i] + heights_and_widths[i+1:])

if (current_height, current_width) not in cache:
cache[(current_height, current_width)] = largest_tower_memoized(
subarray, current_height, current_width, cache
)

I find this more complicated to explain. My intuition tells me that it's O(n), since we the recursion tree for each input is generated only once, but I'm not sure.
• Have you tried the "counting method"? Add a counter to record how many times the intended operations have been performed. Print it out at the end. Now run your program with different $n$, which should give you clues to its asymptotic behavior. – John L. Mar 24 '19 at 21:23