Big O Notation reliability? Is Big-O notation always reliable?
For example:
Algorithm A: $n * 10^{100} = \mathcal{O}\left(n\right)$
Algorithm B: $n^{1.001} = \mathcal{O}\left(n^{1.001}\right)$ 
According to Big-$\mathcal{O}$ notation, Algorithm $A$ would be more efficient, yet for all practical purposes Algorithm $B$ is more efficient. In a situation like this, wouldn't Big-O notation fail? Is there a way to avoid such problems?
 A: The concept involves "when $n$  is large". The antidote to your problem involves noticing that "large enough to be 'large'" varies between contexts (sometimes 2 is large enough). It looks like your context is too small to be "large" ... and this always needs checking.
A: this concept (that the big O notation is useless for small $n$) is known and why tuning of algorithms for specific $n$s happens 
for example insertion sorting 5 elements in place is faster that using quicksort and this is why many implementations have a if(length<5)do insertion sort guard clause in the recursion
in your example this would mean that you would switch algorithms depending on whether $n^{1.001} \lt 100*n$ or $n\lt100^{100}$
A: This should be a comment, but there isn't enough room. 
There are a number of real life problems where the distinction between fastest theoretical runtime and fastest practical algorithm is apparent. The simplest example I know of is matrix multiplication.
Multiplying two $n\times n$ square matrices is obviously at least $O(n^2)$, but with the algorithm that comes strait from the definition it is $O(n^3)$. For practical purposes, the best algorithm is the Strassen Algorithm in most cases, which is approximately $O(n^{2.807})$. The fastest known algorithm in theory is the Coppersmith–Winograd algorithm, at a much faster $O(n^{2.3727})$. But in practice, the smallest matrices for which this is actually faster than the Strassen algorithm are large enough that they just can't be multiplied on modern computers, regardless of what algorithm you pick.
Incidentally, it's suspected that one can have $O(n^2)$ matrix multiplication (perhaps with some extra sublinear factors), but how to do it has been open for a long time.
So, if by $O$ being reliable, you mean that the fastest algorithm in theory is actually the most useful for practical data sets, the answer is no. On the other hand, what is practically useful is much harder to define, which is why $O$ and its variants are the ways people usually study algorithms.
A: For any two algorithms with different order (big-$\mathcal{O}$) complexity, we can calculate the actual ratio of their complexity as a function of n.  Being a bit more general in your case by using symbolic constants, and assuming there are no other constant multiplicative or additive factors, we get 
$R=$ exponential/linear $=n^b/{(n\cdot 10^a)}=n^{b-1}/10^a$, with $a=100, b=1.001$ for your example
Calculate the "crossover point" by setting $R=1$ and solving, giving 
$n=10^{a/{(b-1)}}$. 
Plug in your values and you get that these two algorithms "cross" at 
$n=10^{100/.001}=10^{100000}$ or 10 followed by 100,000 zeros.
Indeed that's an astronomically large number, nope, even bigger than astronomical, probably one of those silly metaphors like more than the number of electrons if all of known space were packed tightly with them. So, yes, anything even remotely practical should be done with the "exponential" algorithm in this case.
But if $a = .5, b = 1.1$ you'd get the crossover at $n=10^5=$ 100,000.  So, if $n>$ 100,000 you'd prefer the linear algorithm, and if $n=$ 1,000,000, which is not at all unreasonable, the linear algorithm is faster by a factor of $R \approx$ 7.96, and the ratio grows exponentially for larger $n$.
So, yes, $\mathcal{O}$ analysis is quite reliable, and a very useful tool for evaluating algorithms.
