f∈Θ(g) is equivalent to f∈O(g)∧g∈O(f). This isn't really a "tight upper bound." For your spikey function f above, we have f∈O(n^2) and f∈Ω(n). These bounds a

f∈Θ(g) is equivalent to f∈O(g)∧g∈O(f). This isn't really a "tight upper bound." For your spikey function f above, we have f∈O(n^2) and f∈Ω(n). These bounds are tight in the sense that there are no strictly tighter bounds. That is, there exists no function g with f∈O(g)∧g∈o(n^2) (there is no function asymptotically smaller than n^2 that bounds f from above). So for this f one could reasonably consider n^2 to be a "tight upper bound", although one would need to pick a spikey bounding function to say anything involving f and Θ. The problem of having an infinite number of inputs of size n is usually not a problem, because there are finitely many bit strings of each length. If an algorithm uses subroutines that act on input objects of unbounded length (like comparing arbitrary-precision integers), and you are only interested in the bound for the number of subroutine calls, then there might be some trouble with the notion of an average case across a fixed input size. This is a bit silly though; it's more a way to define "fixed input size" into describing "unboundedly large input size" than something I would actually want to do for some useful purpose.