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

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.

• The test in the optimization seems to be the wrong way around. You should be checking for >=, not <=. Nov 6, 2019 at 14:46
• @TomvanderZanden You're right, thank you.
– Zyx
Nov 6, 2019 at 14:51

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.