Nontrivial problems solvable in constant time?
The paper Constant-Time Approximation Algorithms via Local Improvements by Nguyen and Onak gives a lot of examples of random constant time approximation schemes: Maximum Matching (the running time depends only on the maximum degree of the graph), Set cover, etc. The authors present a method to design such algorithms.