I'm a bit confused on how to determine when constant is important to find big O. I know we're supposed to ignore constant to find big O but this function is making me think twice:
f(n): 5n + 8n log n + 3 000 000
I'd think this is O(n log n) but if n starts as small values, f(n) will stay around 3 000 000. So should i look at these type of functions as if n is a very large value? But if I do that, would that be realistic since most code doesn't have a 10 000 sample size?
When you calculate the Big-O for a function you always want to think of very,very large numbers. That helps you determine the performance of your function when the sample size goes to infinity (in other words, when it grows very very large).
Usually, after you compute the Big-O you will also want to look for the n0 number. You can think of this n0 number as the tipping point. The performance of the function with any number larger than n0 will be equal to Big-O. For smaller numbers, the performance will be dictated by the constants, or other factors in the function. That is why the Big-O alone is not sufficient when assessing the performance of a function (although it's the first thing you should determine). After you determine the Big-O, you should benchmark or time your function and determine the n0 tipping point and determine what sample sizes, or number of items, will your function process the majority of the time.
Sometime you will write functions that will work on relatively small sets of numbers (say 10s or 100s) and some times your functions will be expected to process items on the order of millions or billions.
Big O notation is used to find the limiting behaviour as the argument grows to infinity. That's why you ignore the constant: it gets swamped out as n gets larger and larger.
Check out the answers (particularly the highest-scoring one) of this question for further details.
But you've hit upon one of the limitations of mindlessly following Big O: there are always other considerations. Your constant could actually be quite large (as in your case) and your values of n are always going to be small (as in your case), so effectively your algorithm is O(1). However, technically speaking, it's O(n log n), because you're supposed to ignore the constant.
You should consider the constant when your data size/input is small. But since while developing these algorithms, upper bound is not considered, constants are ignored.
For example:
Both: merge sort and quick sort is nlogn. But quicksort has a small constant factor, that s why it behaves faster for small input compared to merge sort.
