Determining whether a change in an memoized algorithm will improve the performance

Question

I have an algorithm that constructs an optimal binary tree using dynamic programming. After introducing what I thought would be an optimization, the algorithm became over 2 times slover. Question: Is there an analytical way to determine whether such change will improve the runtime of an algorithm with memoization?

Python code and description follow:

def solver(problem, memo={}):
    try:
        return memo[problem]
    except KeyError:
        if is_base_case(problem):
            memo[problem] = base_solver(problem)
            return memo[problem]

    best_score, best_solution = INFINITY, None

    for left_subproblem, right_subproblem in all_splits(problem):

        left_solution = solver(left_subproblem, memo)

        if (base_score(problem) + score(left_solution) >= best_score):  #optimization
            continue                                                #optimization

        right_solution = solver(right_subproblem, memo)

        current_score = base_score(problem) + score(left_solution) + score(right_solution)
        if (current_score < best_score):
            best_score = current_score
            best_solution = combine_solutions(problem, left_solution, right_solution)

    memo[problem] = best_solution
    return memo[problem]

The function iterates over all ways to split an instance problem into two subproblems, recursively solves them and stores the solutions.
Optimal tree is a tree that has the lowest score, determined by the score() function. The score of a tree is always positive and is a sum of a base score of the root node plus the score of the subtrees.
The optimization in question are the lines marked as #optimization. It's supposed to avoid solving the right subproblem, if, based on the left result, it's impossible to create a solution with a better score than the current best.
Intuitively I understand that the reason why the function became less efficient is because it avoids solving the right subproblem sometimes, which means that it also memoizes less cases, which in turn makes it perform more work. However, this is just my hindsight and I would like to have a rigorous way to analyse the problem, in case an algorithm like this was presented to me in pseudo-code.

Answer 1

Intuitively I understand that the reason why the function became less efficient is because it avoids solving the right subproblem sometimes, which means that it also memoizes less cases, which in turn makes it perform more work.

This is impossible. Not solving and memoizing a subproblem can never make the algorithm slower. Either the subproblem will never be needed (in which case not memoizing it only saves work) or it will turn out to be necessary after all, in which case we would have to compute it. However, the worst case is only that we do not save any time: if we skip the computation now, we might have to do it in the future, but this is not more work than doing it now.

The optimization you've done will never cause more work to be done on computing subproblems. Thus, the only reason it could make the algorithm slower is if the optimization itself is expensive to compute. It seems likely either score or base_score are very slow methods, and your optimization causes them to be evaluated an additional time. You might be able to speed it up by storing base_score and score(left_solution) in a temporary variable.