Not according to my understanding of the subject, my copy of "Introduction to Algorithms", and Wikipedia. Big O is an upper bound for a function growth - being

Not according to my understanding of the subject, my copy of "Introduction to Algorithms", and Wikipedia. Big O is an upper bound for a function growth - being O(f(n)) means growing asymptotically slower than f(n) (up to a multiplication by a constant). Small o is a lower bound for a function growth - being o(f(n)) means growing asymptotically faster than f(n) (up to a multiplication by a constant). Big theta means the function grows exactly that fast - being Θ(f(n)) means the function is both O(f(n)) and o(f(n)), so being exactly f(n) up to a multiplication by a constant. In practice, due to typographical limitations, people use O(n) where Θ(n) would be more precise. Average case, best case, worst case, amortized etc complexities are a wholly different thing. For example, quick sort is Θ(n^2) worst case and Θ(n log n) average case.