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?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
$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.
-
$\begingroup$ 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)$. $\endgroup$ Feb 27, 2021 at 12:22
$\begingroup$
$\endgroup$
1
$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.
