User loginNavigation |
Proving running times of algorithmsBack in university, I only learned to analyse running times of simple imperative algorithms. I don't see how the techniques extend to higher order algorithms, or ones that rely on lazy evaluation. I've looked at papers describing lazy algorithms, but their running times are only analysed in hand-waving form. Is that the best anyone can do, or are there better ways? I haven't seen anything even attempt to describe the running time of higher order algorithms. I'm exploring for my own interest adding support for proofs of worst-case running time to a lazy language with first-class functions, possibly using dependent types, and I'm trying to see what notation and techniques are already used out there for doing the proofs by hand. So, got any papers or languages relevant to this? By jason stumpf at 2009-09-03 23:45 | LtU Forum | previous forum topic | next forum topic | other blogs | 6141 reads
|
Browse archives
Active forum topics |
Recent comments
6 weeks 14 hours ago
6 weeks 18 hours ago
6 weeks 18 hours ago
28 weeks 1 day ago
32 weeks 3 days ago
34 weeks 1 day ago
34 weeks 1 day ago
36 weeks 5 days ago
41 weeks 3 days ago
41 weeks 3 days ago