Do you know sensible algorithms that run in polynomial time in (Input length + Output length), but whose asymptotic running time in the same measure has a really huge exponent/constant (at least, where the proven upper bound on the running time is in such a way)?
Polynomial-time algorithms with huge exponent/constant
ds.algorithms;big list
Algorithms based on the regularity lemma are good examples for polynomial-time algorithms with terrible constants (either in the exponent or as leading coefficients).The regularity lemma of Szemeredi tells you that in any graph on $n$ vertices you can partition the vertices into sets where the edges between pairs of sets are pseudo-random (i.e., densities of sufficiently large subsets look like densities in a random graph). This is a structure that is very nice to work with, and as a consequence there are algorithms that use the partition.The catch is that the number of sets in the partition is an exponential tower in the parameter of pseudo-randomness (See here: http://en.wikipedia.org/wiki/Szemer%C3%A9di_regularity_lemma).For some links to algorithms that rely on the regularity lemma, see, e.g.:http://www.cs.cmu.edu/~ryanw/regularity-journ.pdf