Does the O(n) algorithm always run faster than the O(n^3) algorithm? Why?

Assuming that the time complexity of the two algorithms $$A_1$$ and $$A_2$$ to solve the same problem are $$O(n^3)$$ and $$O(n)$$ respectively. If you write programs for these two algorithms and run them in the same environment, does the program of algorithm $$A_2$$ run faster than algorithm $$A_1$$ for sure? why?

$$O(f(n))$$ means: There is a constant c > 0, and an integer $$n_0$$, so that for every $$n > n_0$$ the time is less than $$c \cdot f(n)$$.

Note that the integer $$n_0$$ could be very, very large. And the constant c could be very, very large. If $$n ≤ n_0$$ then we know nothing whatsoever about the time; the $$O(n)$$ algorithm could be slower than the $$O(n^3)$$ algorithm until n is really large. And the constants could be very different. You could have an algorithm that takes $$n$$ years, and another that takes $$n^3$$ nanoseconds.

Just for fun, try to figure out for which n the O(n) algorithm is faster, and how long it runs when it runs faster. For example with n = 1,000,000 the first algorithm takes a million years, the second takes $$10^{18}$$ nanoseconds = $$10^9$$ seconds < 32 years.

PS. When you look closely at the definition of $$O(f(n))$$, it doesn't actually say that our function must be anywhere near f(n). For example, $$n^{1/2} = O(n^3)$$ according to the definition. You'll often see $$\Theta(f(n))$$ (big-Theta) which means your function isn't just less than c * f(n) but between c1 * f(n) and c2 * f(n). And there are situations where a function doesn't behave the same for all values. Say sometimes it's close to n^3, but at other values n it's much smaller. If f(n) cannot be replaced with a smaller function then we call it "asymptotic O(f(n))".

So you could have f(n) = n if n is even, 1 otherwise. And g(n) = 1 if n is even, n^3 otherwise. For even n, f(n) is larger, for odd n, g(n) is larger.

• The $O(n)$ algorithm could alway be slower than the $O(n^3)$ algorithm, because $O(n^3)$ only gives an upper bound. For example, $f(n) = 10000n \in O(n)$ and $g(n) = 10^{-18}n \in O(n^3)$. – Nathaniel Feb 27 at 12:22

$$O(n)$$ is subset of $$O(n^3)$$ i.e. $$O(n) \subset O(n^3)$$, which means, that algorithm which have $$O(n)$$ complexity also have $$O(n^3)$$. To be sure that one algorithm runs slower, then another, we need it to be in $$O(n^3) \setminus O(n)$$ or $$O(n^3) \cap \Omega(n)$$.

For explanation let's think about big-$$O$$ as about inequality - to be less then $$n$$ always mean to be less then $$n^3$$. To be less, then $$n^3$$ does not guarantee to be less then $$n$$, unless we explicitly require it.

• I understood it perfectly! thank you! – t24akeru Feb 27 at 10:55