Recurrence relations based on minimization and maximization (Q1079343): Difference between revisions

From the article: Explicit and asymptotic solutions are presented to the recurrence \(M(1)=g(1)\), \[ M(n+1)=g(n+1)+\min_{1\leq t\leq n}(\alpha M(t)+\beta M(n+1-t)) \] for the cases (1) \(\alpha +\beta <1\), \(\log_ 2\alpha /\log_ 2\beta\) is rational, and \(g(n)=\delta_{n1}\). (2) \(\alpha +\beta >1\), \(\min (\alpha,\beta)>1\), \(\log_ 2\alpha /\log_ 2\beta\) is rational, and (a) \(g(n)=\delta_{n1}\), (b) \(g(n)=1\). Such recurrences arise commonly in the analysis of algorithms, especially algorithms based on dynamic programming or divide and conquer techniques.