Big-O when the value of n gets very small?
big-o
Solution
Big O doesn't describe the execution time of a function, just the growth. All functions have some constant factor or overhead that needs to be added in. When n is low, this overhead can greatly dwarf any improvements to the algorithm - an algorithm that requires 50ms per operation but has O(n) will perform worse for small n than an algorithm that requires 5 ms per operation, but has O(n*n).
This is why, in general, for small sets big O doesn't matter. For most objects with simple comparisons, a quick sort on 10 items will not be noticiably faster than a bubble sort, a linear search on 100 items will probably be faster than a binary tree, and so on.
Problem
I missed the class where big-O was introduced thinking that it was pretty straight forward. It still seems to be however the teacher said something about O(n) deviating from the function when n gets very small? I couldn't find this anywhere in the book. Could someone enlighten me? Our exploration of O(n) has been in the context of sorting algorithms if that is of any significance. Thanks Gene edit: Thanks for the help guys it has been illuminating. I have a follow-up question. Is there a relatively simple mathematical way to figure out the point where n is too small for O(n)? Related questions are there any O(1/n) algorithms? What is the difference between Θ(n) and O(n)?