0

Let's say I have two algorithms, one of which is less efficient in the sense that the complexity in the $\mathcal{O}$ notation has an additional factor $n$ (so for example, one is $\mathcal{O}(n^2)$ while the other is only $\mathcal{O}(n)$.

So how can I express the difference between these two algorithms, not knowing their overall complexity? For example, I may know that $A_1$ and $A_2$ are built using a common building block, but that $A_1$ does the main computation $n$ times while $A_2$ only does it once. Can I say $A_1$ is more complex than $A_2$ by $\mathcal{O}(n)$?

Example:

$A_1$:

for i = 1 : n
    do_something_with_unknown_constant_complexity(...);
end

$A_2$:

do_something_with_unknown_constant_complexity(...);
bers
  • 552
  • 1
  • 4
  • 17
  • With your first sentence, do you mean to say that $\mathcal{O}(\exp(n))$ equals $\mathcal{O}(n\exp(n))$? I agree with the second sentence, but I want to express by how much $A_1$ is better than $A_2$. – bers Jan 19 '16 at 21:07
  • Now you say it, I doubt whether my first sentence is correct. – Peter Jan 19 '16 at 21:13

1 Answers1

1

The premise that an $\mathcal{O}(n^2)$ function is more complex than an $\mathcal{O}(n)$ function is not quite right. The big-$\mathcal{O}$ notation acts more like an upper bound than like an exact equation.

For example, $f(n) = n$ is $\mathcal{O}(n^2)$. Usually we'd say it's $\mathcal{O}(n)$, but it's certainly $\mathcal{O}(n^2)$ too; in fact $\mathcal{O}(n)$ implies $\mathcal{O}(n^2)$.

But you would never want to say that $f(n) = n$ is $\mathcal{O}(n)$ as complex as $g(n) = 2n$, merely because the statements "$f(n) = n$ is $\mathcal{O}(n^2)$" and "$g(n) = 2n$ is $\mathcal{O}(n)$" happen to be true.

If you can show that the ratio $\dfrac{A_1(n)}{A_2(n)}$ is $\mathcal{O}(n)$, then I think it is fine to say that $A_1$ is more complex than $A_2$ by at most a factor of $\mathcal{O}(n)$. In the example you describe, however, you might be able to prove that $\dfrac{A_1(n)}{A_2(n)}$ is $\Theta(n)$, which is a stronger condition, and lets you say that $A_1$ is more complex than $A_2$ by a factor of $\Theta(n)$.

David K
  • 98,388