0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Apass.Jack Mar 24 at 21:23
  • 1
    $\begingroup$ @Apass.Jack Indeed I've had the temptation of doing it but I've discarded. My aim is to be able to infer the time complexity by analysis rather than making some reverse engineering, that's why I focus on the reasoning that led me to the hypothetical result. $\endgroup$ – Julen Mar 24 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.