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 | 6056 reads
|
Browse archives
Active forum topics
|
Recent comments
11 weeks 1 day ago
15 weeks 3 days ago
17 weeks 15 hours ago
17 weeks 15 hours ago
19 weeks 5 days ago
24 weeks 2 days ago
24 weeks 2 days ago
24 weeks 5 days ago
24 weeks 5 days ago
27 weeks 4 days ago