0
$\begingroup$

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?

$\endgroup$

2 Answers 2

4
$\begingroup$

$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.

$\endgroup$
1
  • $\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$
    – Nathaniel
    Feb 27, 2021 at 12:22
0
$\begingroup$

$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.

$\endgroup$
1
  • $\begingroup$ I understood it perfectly! thank you! $\endgroup$
    – t24akeru
    Feb 27, 2021 at 10:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.