python - Complexity analysis of nested recursive functions -


i've written out recursive algorithm little homegrown computer algebra system, i'm applying pairwise reductions list of operands of algebraic operation (adjacent operands only, algebra non-commutative). i'm trying idea of runtime complexity of algorithm (but unfortunately, physicist it's been long time since took undergrad cs courses dealt complexity analysis). without going details of specific problem, think can formalize algorithm in terms of function f "divide" step , function g combines results. algorithm take following formal representation:

f(1) = 1  # recursion anchor f f(n) = g(f(n/2), f(n/2))  g(n, 0) = n, g(0, m) = m            # recursion ... g(1, 0) = g(0, 1) = 1               # ... anchors g             / g(g(n-1, 1), m-1)  if reduction "non-neutral" g(n, m) = |  g(n-1, m-1)        if reduction "neutral"            \ n + m              if no reduction possible

in notation, functions f , g receive lists arguments , return lists, length of input/output lists being argument , right-hand-side of equations above.

for full story, actual code corresponding f , g following:

def _match_replace_binary(cls, ops: list) -> list:     """reduce list of `ops`"""     n = len(ops)     if n <= 1:         return ops     ops_left = ops[:n//2]     ops_right = ops[n//2:]     return _match_replace_binary_combine(             cls,             _match_replace_binary(cls, ops_left),             _match_replace_binary(cls, ops_right))   def _match_replace_binary_combine(cls, a: list, b: list) -> list:     """combine 2 reduced lists a, b"""     if len(a) == 0 or len(b) == 0:         return + b     if len(a) == 1 , len(b) == 1:         return + b     r = _get_binary_replacement(a[-1], b[0], cls._binary_rules)     if r none:         return + b     if r == cls.neutral_element:         return _match_replace_binary_combine(cls, a[:-1], b[1:])     r = [r, ]     return _match_replace_binary_combine(             cls,             _match_replace_binary_combine(cls, a[:-1], r),             b[1:])

i'm interested in worst-case number of times get_binary_replacement called, depending on size of ops

so think i've got now. restate problem: find number of calls _get_binary_replacement when calling _match_replace_binary input of size n.

  • define function g(n, m) (as in original question) maps size of the 2 inputs of _match_replace_binary_combine size of output
  • define function t_g(n, m) maps size of 2 inputs of _match_replace_binary_combine total number of calls g required obtain result. (worst case) number of calls _get_binary_replacement each call _match_replace_binary_combine calls _get_binary_replacement @ once

we can consider worst case , best case g:

  • best case (no reduction): g(n,m) = n + m, t_g(n, m) = 1

  • worst case (all non-neutral reduction): g(n, m) = 1, t_g(n, m) = 2*(n+m) - 1 (i determined empirically)

now, master theorem (wp) applies:

going through description on wp:

  • k=1 (the recursion anchor size 1)
  • we split a = 2 subproblems of size n/2 in constant (d = 1) time
  • after solving subproblems, amount of work required combine results c = t_g(n/2, n/2). n-1 (approximately n) in worst case , 1 in best case

thus, following examples on wp page master theorem, worst case complexity n * log(n), , best case complexity n

empirical trials seem bear out result. objections line of reasoning?


Comments

Post a Comment