[HN Gopher] Formal proof and analysis of an incremental cycle de... ___________________________________________________________________ Formal proof and analysis of an incremental cycle detection algorithm Author : lelf Score : 21 points Date : 2020-02-20 05:34 UTC (17 hours ago) (HTM) web link (gallium.inria.fr) (TXT) w3m dump (gallium.inria.fr) | superpermutat0r wrote: | I remember reading somewhere about programs being turned into | generating functions and then asymptotic complexity follows from | that. Not just asymptotic in the worst-case but also the best- | case and average case. | | It did not require a formal proof. It just turned code into | generating functions. | | It was probably work by Philippe Flajolet, also at Inria. | | I think I also remember it being used for memory reads and writes | in addition to comparison ops analysis. | | Really great stuff. ___________________________________________________________________ (page generated 2020-02-20 23:00 UTC)