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(...);
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)$.