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:]
results.add(1 + largest_tower(subarray, current_height, current_width))
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
)
results.add(1 + cache[(current_height, current_width)])
return max(results)
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.
