The empirical curve bounding problem is defined asfollows. Suppose data vectors X,Y are presented such that ]]> where ]]> is an unknown function. The problemis to analyze X,Y and obtain complexity bounds O(g_u(x)) and]]> on the function ]]>. As no algorithm for empirical curve bounding can be guaranteedcorrect, we consider heuristics. Five heuristic algorithms arepresented here, together with analytical results guaranteeingcorrectness for certain families of functions. Experimentalevaluations of the correctness and tightness of bounds obtained by therules for several constructed functions ]]> and real datasetsare described. A hybrid method is shown to have very good performanceon some kinds of functions, suggesting a general, iterative refinementprocedure in which diagnostic features of the results of applyingparticular methods can be used to select additional methods.